A Turing Machine for the language \(\mathrm{L}=\left\{\mathrm{a}^{\mathrm{n}}…

PYQ UGC NET 2022Modified — slightly modified from the official paper; see the solution

 A Turing Machine for the language L={anbmcndm∣n≥1, m≥1}\mathrm{L}=\left\{\mathrm{a}^{\mathrm{n}} \mathrm{b}^{\mathrm{m}} \mathrm{c}^{\mathrm{n}} \mathrm{d}^{\mathrm{m}} \mid \mathrm{n} \geq 1, \mathrm{~m} \geq 1\right\} is designed. The resultant model is M=M =({q0,q1,q2,q3,q4,q5,q6,q7,qf},{a,b,c,d},{a,b,c,d,X1,X2,Y1,Y2},δ,q0, B,{qf})\left(\left\{\mathrm{q}_{0}, \mathrm{q}_{1}, \mathrm{q}_{2}, \mathrm{q}_{3}, \mathrm{q}_{4}, \mathrm{q}_{5}, \mathrm{q}_{6}, \mathrm{q}_{7}, \mathrm{q}_{\mathrm{f}}\right\},\{\mathrm{a}, \mathrm{b}, \mathrm{c}, \mathrm{d}\},\left\{\mathrm{a}, \mathrm{b}, \mathrm{c}, \mathrm{d}, \mathrm{X}_{1}, \mathrm{X}_{2}, \mathrm{Y}_{1}, \mathrm{Y}_{2}\right\}, \delta, \mathrm{q}_{0}, \mathrm{~B},\left\{\mathrm{q}_{\mathrm{f}}\right\}\right) and part of ′ 𝛿 ′' 𝛿 ' is given in the transition table. You need to write the following questions based on design of Turing Machine for the given language. Note that, while designing the Turing Machine X1X_1 and X2X_2 are used to work with ′𝑎′𝑠′𝑎′𝑠 and ′𝑐′𝑠′𝑐′𝑠 and Y1Y_1 and Y2Y_2 are used to handle ′𝑏′𝑠′𝑏′𝑠 and ′𝑑′𝑠′𝑑′𝑠 of the given string.

abcdX1X2Y1Y2 Bq0(q1,X1,R)M2q1(q1,a,R)(q1, b,R)M1(q1,X2,R)q2(q2,a,L)(q2, b, L)(q2,X1,R)(q2,X2, L)q3M3(q4,Y1,R)(q6,X2,R)q4(q4, b,R)(q5,Y2, L)M5(q4,Y2,R)q5(q5, b, L)(q5,X2, L)M4(q5,Y2, L)q6(q6,X2,R)(q7,Y2,R)q7(q7,Y2,R)(qf, B,R)\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline & \mathrm{a} & \mathrm{b} & \mathrm{c} & \mathrm{d} & \mathrm{X}_{1} & \mathrm{X}_{2} & \mathrm{Y}_{1} & \mathrm{Y}_{2} & \mathrm{~B} \\ \hline \mathrm{q}_{0} & \left(\mathrm{q}_{1}, \mathrm{X}_{1}, \mathrm{R}\right) & & & & \mathrm{M} 2 & & & & \\ \hline \mathrm{q}_{1} & \left(\mathrm{q}_{1}, \mathrm{a}, \mathrm{R}\right) & \left(\mathrm{q}_{1}, \mathrm{~b}, \mathrm{R}\right) & \mathrm{M} 1 & & & \left(\mathrm{q}_{1}, \mathrm{X}_{2}, \mathrm{R}\right) & & & \\ \hline \mathrm{q}_{2} & \left(\mathrm{q}_{2}, \mathrm{a}, \mathrm{L}\right) & \left(\mathrm{q}_{2}, \mathrm{~b}, \mathrm{~L}\right) & & & \left(\mathrm{q}_{2}, \mathrm{X}_{1}, \mathrm{R}\right) & \left(\mathrm{q}_{2}, \mathrm{X}_{2}, \mathrm{~L}\right) & & & \\ \hline \mathrm{q}_{3} & \mathrm{M} 3 & \left(\mathrm{q}_{4}, \mathrm{Y}_{1}, \mathrm{R}\right) & & & & \left(\mathrm{q}_{6}, \mathrm{X}_{2}, \mathrm{R}\right) & & & \\ \hline \mathrm{q}_{4} & & \left(\mathrm{q}_{4}, \mathrm{~b}, \mathrm{R}\right) & & \left(\mathrm{q}_{5}, \mathrm{Y}_{2}, \mathrm{~L}\right) & & \mathrm{M} 5 & & \left(\mathrm{q}_{4}, \mathrm{Y}_{2}, \mathrm{R}\right) & \\ \hline \mathrm{q}_{5} & & \left(\mathrm{q}_{5}, \mathrm{~b}, \mathrm{~L}\right) & & & & \left(\mathrm{q}_{5}, \mathrm{X}_{2}, \mathrm{~L}\right) & \mathrm{M} 4 & \left(\mathrm{q}_{5}, \mathrm{Y}_{2}, \mathrm{~L}\right) & \\ \hline \mathrm{q}_{6} & & & & & & \left(\mathrm{q}_{6}, \mathrm{X}_{2}, \mathrm{R}\right) & & \left(\mathrm{q}_{7}, \mathrm{Y}_{2}, \mathrm{R}\right) & \\ \hline \mathrm{q}_{7} & & & & & & & & \left(\mathrm{q}_{7}, \mathrm{Y}_{2}, \mathrm{R}\right) & \left(\mathrm{q}_{\mathrm{f}}, \mathrm{~B}, \mathrm{R}\right) \\ \hline \end{array}


What is the Move in the cell with number ′M4′'M4' of the resultant Table?

Assume q5 scans left across previously marked Y1 symbols without changing them.

  1. A.

    (q5,Y1, L)\left(\mathrm{q}_{5}, \mathrm{Y}_{1}, \mathrm{~L}\right)

  2. B.

    (q3,Y1,R)\left(\mathrm{q}_{3}, \mathrm{Y}_{1}, \mathrm{R}\right)

  3. C.

    (q4,Y1, L)\left(\mathrm{q}_{4}, \mathrm{Y}_{1}, \mathrm{~L}\right)

  4. D.

    (q3,Y1, L)\left(\mathrm{q}_{3}, \mathrm{Y}_{1}, \mathrm{~L}\right)

Attempted by 58 students.

Sign up free to check your answer

Sign up free

Explore the full course: Nta Ugc Net Paper 2

Loading lesson…