Theory of Computation TU Board 2081 question paper

Mention the transition function of PDA. List the two ways that PDA accepts the string. Convert the following CFG to PDA.
S → AS | ε
A → Ab | Bb | ab

List any two regular operators. Minimize the following finite state machine using Table Filling algorithm.

[figure in the original paper]

Define Turing machine as enumerators of strings of a language. Encode the Turing machine TM = ({q_0, q_1, q_2} , {a, b}, {a, b, B}, δ, q_2, B, F) with input w = ba and δ is defined as follows:
δ(q_0, b) → (q_1, b, R), δ(q_1, a) → (q_2, a, R), δ(q_2, a) → (q_1, a, R), δ(q_2, b) → (q_2, b, L)

Does machine always refer to hardware? Justify. Define positive closure and Kleene closure.

What is undecidable problem? Discuss about Post Correspondence Problem.

Define the language of a grammar. For the grammar S → 0S0 | 1 | ε, show the leftmost derivation for the string 00100 with its parse tree.

Define ε-closure of a state. Differentiate between Moore and Mealy machine.

Represent the following regular grammar to finite automata.
S → aA | aB | ε
A → aA | aS
B → bB | ε

Design the DFA that accepts binary string ending with "00" and show its extended transition function for the string 111000.

Convert the following grammar to CNF.
S → AAB, A → aA | ε, B → ab | a

11. For the following Turing Machine, test whether the string "( ) ( )" is accepted or rejected and represent it in transition diagram. [5]

State
(
)
X
Y
B
q_0
(q_1, X, R)
–
–
(q_0, Y, R)
(q_3, B, R)
q_1
(q_1, (, R)
(q_2, Y, L)
–
(q_1, Y, R)
–
q_2
(q_2, (, L)
–
(q_0, X, R)
(q_2, Y, L)
–
q_3
–
–
–
(q_3, Y, R)
(q_4, B, R)
q_4
–
–
–
–
–

Differentiate between Class P and Class NP problem. Mention the transition function of DFA, NFA, and ε-NFA.