Skip to content

Instantly share code, notes, and snippets.

@Teemu
Last active March 14, 2016 11:16
Show Gist options
  • Save Teemu/34ae082c04bd47c74657 to your computer and use it in GitHub Desktop.
Save Teemu/34ae082c04bd47c74657 to your computer and use it in GitHub Desktop.
Turing machine that detects {ww | w contains {a,b}*}, try it at http://turingmachinesimulator.com/shared/gfemhnbiqs
name: ww
init: Start
accept: Success
Start,a,_
GoRight,a,X,>,>
Start,b,_
GoRight,b,X,>,>
Start,a,Y
2GoLeft,a,Y,<,<
Start,b,Y
2GoLeft,b,Y,<,<
GoRight,a,_
GoRight,a,_,>,>
GoRight,b,_
GoRight,b,_,>,>
GoRight,_,_
End,_,_,<,<
GoRight,a,Y
End,a,Y,<,<
GoRight,b,Y
End,b,Y,<,<
End,a,_
GoLeft,a,Y,<,<
End,b,_
GoLeft,b,Y,<,<
GoLeft,a,_
GoLeft,a,_,<,<
GoLeft,b,_
GoLeft,b,_,<,<
GoLeft,a,X
Start,a,X,>,>
GoLeft,b,X
Start,b,X,>,>
2GoLeft,a,X
2GoLeft,a,X,<,<
2GoLeft,b,X
2GoLeft,b,X,<,<
2GoLeft,a,@
2GoLeft,a,@,<,<
2GoLeft,b,@
2GoLeft,b,@,<,<
2GoLeft,a,#
2Copy,a,#,>,>
2GoLeft,b,#
2Copy,b,#,>,>
2GoLeft,_,_
2Copy,_,_,>,>
2Copy,a,X
2CopyLetterA,a,#,>,>
2Copy,b,X
2CopyLetterB,b,#,>,>
2Copy,a,@
Success,a,@,-,-
2CopyLetterA,a,X
2CopyLetterA,a,X,>,>
2CopyLetterA,b,X
2CopyLetterA,b,X,>,>
2CopyLetterA,a,@
2CopyLetterA,a,@,>,>
2CopyLetterA,b,@
2CopyLetterA,b,@,>,>
2CopyLetterA,a,Y
2GoLeft,a,@,<,<
2CopyLetterB,a,X
2CopyLetterB,a,X,>,>
2CopyLetterB,b,X
2CopyLetterB,b,X,>,>
2CopyLetterB,a,@
2CopyLetterB,a,@,>,>
2CopyLetterB,b,@
2CopyLetterB,b,@,>,>
2CopyLetterB,b,Y
2GoLeft,b,@,<,<
@mugartec
Copy link

Thanks for sharing this. Would it be possible to add this machine to the examples of the website?
I have a small suggestion regarding the description of the machine: changing contains by matches. It got me confused at the beginning because I thought that w should only contain a sub-word matching {a,b}*, and then the machine would accept words like abcabc (which I realized do not match since there is no c on the code).

Thanks again!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment