__a__a#

(a, Y, R)

Y

__a__#

(a,a,R)

Ya

__#__
(#,#,L)

Y

__a__#

(a,X,L)

__Y__X#

(Y,Y,R)

Y

__X__#

No edge out of q6... crash

I think it may help to make the lines between q1 q2 q5 q6 a rectangle. Then one sees straight away the a edge going down, and the a edge coming back up. Add the one edge you enter by, and there are always 2n + 1 a's. As far as the number goes it doesn't matter if you branch to b for your next one.

I think it does accept ODDPALINDROME then.

Your Odd machine looks right, too (although one could "play Planarity" with it

) Two of the ways to skin this same cat? I suppose that topologically that would mean that in some sense both the graphs are equal. Which is probably too interesting a question to be considering at this hour...

__a__
A

__#__
__A__#

halt.