// labc.tm // accept the language L = { a^n b^n c^n | n>0 } // use check off a->X, b->Y, c->Z accept on XY*Z* final q6 start q0 limit 100 trace all q0 a q1 X R // mark off one a q0 Y q4 Y R // no more a's check for no more b's and c's q1 a q1 a R // skip a's q1 Y q1 Y R // skip Y's q1 b q2 Y R // mark off one b q2 b q2 b R // skip b's q2 Z q2 Z R // skip Z's q2 c q3 Z L // mark off one c, go to rewind q3 a q3 a L // rewind q3 b q3 b L // rewind q3 Y q3 Y L // rewind q3 Z q3 Z L // rewind q3 X q0 X R // stop rewind, look for 'a' q4 Y q4 Y R // skipping Y's must have only Z's q4 Z q5 Z R // now should have only Z's q5 Z q5 Z R // any thing except Z or end-of-tape dies q5 #] q6 ## N // accept q6 #] q6 ## N // done, off end accept enddef tape abc accept tape aabbcc accept tape aabc reject