How to construct and write down a Turing machine for a given language?

Question Detail: 

In my class we just started learning about Turing machines. I think I understand the concept but am unsure how to syntactically solve any problem related to one. I am presented with the problem:

Build a Turing machine accepting $(b + c)^+$$\#a^+$ (Please comment your code. Any uncommented solutions will not be graded.)

I am unsure of how to actually begin devising this machine? Could someone please help get me started?

Asked By : Matt Hintzke

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11542

Answered By : Patrick87

What all strategies to devise a program for a Turing machine - or for any other machine, for that matter - boil down to is this: learn how to write programs for easy languages, and then use these programs and rules of composition to figure out more complicated ones. Programming languages - including Turing machine programs - expose an interface to the underlying computer, which allows you to perform some limited number of operations. Programming is the art and science of finding a sequence of such operations to solve your problem.

1. Can you write a Turing machine to recognize $a^+$?
2. Change the Turing machine in (1) to recognize $\#$ only. Hint: it's a different symbol and you only want one of them.
3. Change the Turing machine in (1) to recognize $(b + c)^*$. Hint: you'll now take either of two symbols instead of one symbol.
4. Take the machines from steps (3), (2) and (1). Create a new machine that does what (3) does, but instead of accepting, it does what (2) does, but instead of accepting, it does what (1) does.

In TM pseudocode, what you get is something along the following lines:

1. Move one cell to the right.
2. If the cell is $b$ or $c$, move to the right; else, halt reject.
3. If the cell is $b$ or $c$, move to the right, and repeat this step. Otherwise, if the cell is $\#$, move to the right and go to the next step. Halt reject in any other case.
4. If the cell is $a$, move to the right; else, halt reject.
5. If the cell is $a$, move to the right. Else, if the cell is blank, halt accept. Halt reject in any other case.

Those would serve as decent comments, but coming up with the TM and verifying that it works should also accompany any correct answer.