Example 8.1.1: a Turing recognizer for {0n1n | n1}.
transition comment
s00s1Xr mark a 0 with X and goto search for a corresponding 1
s0Ys3Yr no more 0s remain, goto check that all 1s have been matched
s10s10r move right over 0s and Ys to reach corresponding 1
s1Ys1Yr
s11s2Yl mark corresponding 1 with Y and go back for next 0
s20s20l move left over 0s and Ys to reach last (rightmost) marked 1
s2Ys2Yl
s2Xs0Xr go to repeat for next 0
s3Ys3Yr check no unmarked symbols before end of input
s3bs4bl if so, accept
Previous slide | Next slide | Back to first slide | View graphic version |