CSIT 4th Semester
Theory Of Computation Board Question Paper 2081

Mention the transition function of PDA. List the two ways that PDA accepts the string. Convert the following CFG to PDA.
\(S \rightarrow AS \mid \epsilon\)
\(B \rightarrow aAb \mid Bb \mid ab\)

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

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\}, \delta, q_0, B, F)\), with input \(w: ba\) and \(\delta\) is defined as follows.
\(\delta(q_0, b) = (q_1, a, R)\), \(\delta(q_1, a) = (q_1, b, R)\), \(\delta(q_2, b) = (q_1, a, R)\), \(\delta(q_1, 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's Correspondence Problem.

Define the language of a grammar. For the grammar \(S \rightarrow 0S0 \mid 0 \mid 1 \mid \epsilon\), show the leftmost derivation for the string 00100 with its parse tree.

Represent the following regular grammar to finite automata.
\(S \rightarrow a \mid aA \mid bB \mid \epsilon\)
\(A \rightarrow aA \mid aS\)
\(B \rightarrow bS \mid \epsilon\)

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 \rightarrow AAB\), \(A \rightarrow aAb \mid \epsilon\), \(B \rightarrow aB \mid a\)

For the following Turing Machine, test whether the string "( ) ) (" is accepted or rejected and show it in transition

Differentiate between Class P and Class NP problem. Mention the transition function of DFA, NFA and \(\epsilon\) - NFA.