2013 April 26,

CS 254: Day 12

Carleton College, Spring 2013

Prof. Joshua R. Davis, , CMC 325, x4473

A. In class, we've outlined how to construct a Turing machine to decide the language {anbncn : n ≥ 0}. For your homework, draw out the entire Turing machine, including its preprocessing steps and its acceptance/rejection tests. To improve readability, organize your Turing machine into sections, and annotate these sections — just as you would organize a program into sections with comments or other documentation. (I do not plan to ask you to draw an entire non-trivial Turing machine again in this course.)

B. 3.12

C. 3.13