Question

Can you give me a turing machine for the language c* n b*2n a* n+2 for n>=0 . Please give the entire diagram with states, transition function, alphabet. Can use either one-tape or two-tape (both infinite). Describe the logic used to build the machine. Run the TM that accepts for any string of length > 1. Also run for string cbba.

Answer 1

Solution

The alphabet set is ∑ = {a,b,c}

The strings of the language are {aa,cbbaaa , ccbbbbaaaa , cccbbbbbbaaaaa , ccccbbbbbbbbaaaaaa , ...................}

The turing machine that accepts cⁿb²ⁿaⁿaa is shown below:

Few strings accepted and rejected by the above Turing machine are shown below:

Logic

Traverse the string from left to right, and each time pick one, c convert it to X. Skip all c's in between and convert the first two unchanged b's to Y. Skip all b's and convert the first unchanged a to Z.

Move backwards to find the first unchanged c and repeat the above step.

If the string is accepted than after reppeating above two steps n times the string will have all X's followed by all Y's , followed by all Z and at the end string will have two a's unchanged.

Example:

The steps how string ccbbbbaaaa is accepted is shown below:

ccbbbbaaaa

XcYYbbZaaa

XXYYYYZZaa

Transition function

	a	b	c	X	Y	Z	B
q0	(q6,a,R)		(q1,X,R)		(q5,Y,R)
q1		(q2,Y,R)	(q1,c,R)		(q1,Y,R)
q2		(q3,Y,R)
q3	(q4,Z,R)	(q3,b,R)				(q3,Z,R)
q4	(q4,a,L)	(q4,b,L)	(q4,c,L)	(q0,X,R)	(q4,Y,L)	(q4,Z,L)
q5	(q6,a,R)				(q5,Y,R)	(q5,Z,R)
q6	(q7,a,R)
q7							(q8,B,L)
q8

q0 is the start state and q8 is the final state.

Running string cbba

When the string is placed in the tape it will have a blank symbol B, at the end to mark the end of the string.

cbbaB

q0cbbaB

Xq1bbaB

XYq2baB

XYYq3aB

XYYZq4B

Note that in state q4 there is no transition for Blank symbol B. So since q4 is a non final state , the string is rejected.

Running string cbbaaa

When the string is placed in the tape it will have a blank symbol B, at the end to mark the end of the string.

cbbaaaB

q0cbbaaaB

Xq1bbaaaB

XYq2baaaB

XYYq3aaaB

XYYZq4aaB

XYYq4ZaaB

XYq4YZaaB

Xq4YYZaaB

q0XYYZaaB

Xq5YYZaaB

XYq5YZaaB

XYYq5ZaaB

XYYZq5aaB

XYYZaq6aB

XYYZaaq7B

XYYZaq8aB

Since q8 is a final state the string is accepted by the shown turing machine.