; We assume that the input has a blank at the left
; We want to accept if the input to the right of that is of the
; form w#w for some w in {a,b}*
; We don't care what happens (except we don't accept) otherwise

0 _ _ r matchLtoR

; matchLtoR finds an a or a b to the left and then moves to a
; state of looking for the matching character, or checking if
; finished if there isn't one
matchLtoR a X r right#-a
matchLtoR b X r right#-b
matchLtoR # # r checkFinishedR

; Move to the # symbol and then mark an a to the right of it
right#-a # # r mark-a
right#-a * * r right#-a

right#-b # # r mark-b
right#-b * * r right#-b

; Mark a matching a and find the next character to the right
mark-a a X r matchRtoL
mark-a X X r mark-a

mark-b b X r matchRtoL
mark-b X X r mark-b

; Find the next character to the right, then look for a matching
; character on the left. If there are no more check to the left
; to see if we're finished.
matchRtoL a X l left#-a
matchRtoL b X l left#-b
matchRtoL _ _ l checkFinishedL

left#-a # # l findX-al
left#-a * * l left#-a

left#-b # # l findX-bl
left#-b * * l left#-b

findX-al X X r check-a
findX-al * * l findX-al

findX-bl X X r check-b
findX-bl * * l findX-bl

check-a a X r matchLtoR
check-b b X r matchLtoR

checkFinishedL X X l checkFinishedL
checkFinishedL # # l checkFinishedL
checkFinishedL _ _ * halt-accept

checkFinishedR X X r checkFinishedR
checkFinishedR _ _ * halt-accept