Question

3.(4 4+20-36 points Formal Definition of a Turing Machine (TM) ATM M is expressed as a 7-tuple (Q, T, B, ? ?, q0,B,F) where: . Q is a finite set of states T is the tape alphabet (symbols which can be written on Tape) .B is blank symbol (every cell is filled with B except input alphabet initially .2 is the input alphabet (symbols which are part of input alphabet) is a transition function which maps QxTQxTx (L, R : 90 is the initial state -F is the set of final states. If any state of F is reached, input string is accepted. If the TM M has the transition function ? (Q3,Y,R) qo q1 q2 q3 (q1X.R) (q10R) (a2.YL) (q2,0,L) (q1,YR) (Q3.YR) than: (a) what is Q, T, ? F? (b) what is the language L recognized by the TM M?

Answer 1

(a)

• Q = {q0,q1,q2,q3} where q0 is initial state.
• T = {0,1,X,Y,B} where B represents blank.
• $\Sigma$ = {0,1}
• F = {q3}

(b)

• $L = \{0^n1^n\ |\ n\geq1\}$

Explaination:

Q is the set of states and table contains only 4 states q0,q1,q2 and q3. So Q consists of these 4 states, where q0 is initial state.

T is tape alphabet which will consist of all possible symbols in transition table. so T = {0,1,X,Y,B}

We can see in the transition table that the symbols X and Y are only generated after reading symbols 0 and 1, so X and Y are not part of input alphabet hence $\Sigma$ = {0,1}

The machine halts only in state q3 so F = {q3}

To see the language for turing machine lets see how the machine works on input 0011.

Initially is at the leftmost 0 which is underlined and machine is in state q0 as:

0 0

Then machine will make move ?(q0, 0) = (q1, X, R). It goes to state q1 writing X at the current head position and then moves right as:

Then move will be ?(q1, 0) = (q1, 0, R) which means it will remain in same state and without changing any symbol, it will move to right as:

Then move will be ?(q1, 1) = (q2, Y, L) which means it will move to q2 state and changing 1 to Y, it will move to left as:

0

Working on it in the same way, the machine will reach state q3 and head will point to B as shown:

Using move ?(q3, B) = halt, it will stop and accepted.

The machine similarlly works for the language $0^n1^n$