Q93.Marks: +2.0UGC NET Paper 2: Computer Science 11 March 2023
📄 Passage
A Turing Machine for the language L= {anbmcndm | n ≥ 1, m ≥ 1} is designed. The resultant model is 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}) 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 X1 and X2 are used to work with 'a's and 'c's and Y1 and Y2 are used to handle 'b's and 'd's of the given string.
a
b
c
d
X1
X2
Y1
Y2
B
q0
(q1, X1, R)
M2
q1
(q1, a, R)
(q1, b, R)
M1
(q1, X2, R)
q2
(q2, a, L)
(q2, b, L)
(q3, X1, R)
(q2, X2, L)
q3
M3
(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)
What is the Move in the cell with number 'M5' of the resultant Table?
1.(q4, X2, R)✓ Correct
2.(q5, X2, R)
3.(q5, X2, L)
4.Error Entry
Solution
The correct answer is (q4, X2, R)
Explanation:
State Diagram: L= {anbmcndm | n ≥ 1, m ≥ 1}
X1 and X2 are used to work with 'a's and 'c's
Y1 and Y2 are used to handle 'b's and 'd's
q0 is initial state.
q1, q2, q3, q4, q5, q6, q7 are internal states.
qf is final state.
According to State Diagram We fill the transition table: So M5 is (q4, X2, R)
a
b
c
d
X1
X2
Y1
Y2
B
q0
(q1, X1, R)
Error
q1
(q1, a, R)
(q1, b, R)
(q2, X2, L)
(q1, X2, R)
q2
(q2, a, L)
(q2, b, L)
(q3, X1, R)
(q2, X2, L)
q3
(q1, X1, R)
(q4, Y1, R)
(q6, X2, R)
q4
(q4, b, R)
(q5, Y2, L)
(q4, X2, R)
(q4, Y2, R)
q5
(q5, b, L)
(q5, X2, L)
(q6, Y1, R)
(q5, Y2, L)
q6
(q4, y1, R)
(q6, X2, R)
(q7, Y2, R)
q7
(q7, Y2, R)
(qf, B, R)
Mistake PointsAbove question data is ambiguous so official answer key drop this question. We have updated the question.