Question

Create a DFA for L = {wwR|w ∈ {0, 1}∗}. WR represents the reverse of the string. Explain your answer.

Answer 1

Consider the given language L = {ww^R|w ∈ {0, 1}∗}

L contains the strings of form ww^R. where w belongs to {0,1}*.

L is not a regular language and there exist no DFA to accept L.

A Turing machine M can be implemented that accepts L.

The Turing machine M accepts strings ww^R, where w belongs to {0,1}*.

For example, M accepts 0110,1001,1111,001100, 10100101etc.

• Step1:
  • The Turning machine M scans the input string from left to right as soon as it finds ‘0’, it replaces the cell blank and moves to left until a blank is found.
  • Then moves one step left and if input symbol is ‘0’, then it moves to right until a blank is found.

OR

• • The Turning machine M scans the input string from left to right as soon as it finds ‘1’, it replaces the cell blank and moves to left until a blank is found.
  • Then moves one step left and if input symbol is ‘1’, then it moves to right until a blank is found.
• Step2:
  • Then repeats the above step until all cells become blank.

To implement M first define the states and transition function as follows:

State	Input
	a	b	B
q0	(q1,B,R)	(q2,B,R)	(q6,B,R)
q1	(q1,0,R)	(q1,1,R)	(q3,B,L)
q2	(q2,0,R)	(q2,1,R)	(q4,B,L)
q3	(q5,B,L)	-	-
q4	-	(q5,B,L)	-
q5	(q5,0,L)	(q5,1,L)	(q0,B,R)

DFA(state diagram) that represents M is as follows: