Theory of Computation TU Board 2082 question paper

List the applications of Pumping Lemma. Minimize the following DFA using the Table Filling Algorithm

[figure in the original paper]

Define yield in parse tree with example. Convert the following grammar to CNF:

$\begin{array}{rl}S& \to ASB\mid ϵ\\ A& \to 0AS\mid 0\\ B& \to SIS\mid A\end{array}$

Distinguish between multi-tape and multi-track Turing Machine. Design a TM that accepts a string over the alphabet $\Sigma =\{a,b\}$, such that $L=\{a^n{b}^n\mid n>0\}$.

Why do we need asymptotic notation? Discuss about alphabet and power of alphabet.

Define ambiguous grammar. How do you use parse tree to show the ambiguity of a grammar?

Given the non-deterministic Turing machine, TM = ({q0, q1, q2, qf}, {0, 1}, {0, 1, B}, δ, q0, B, {qf}) with the following transition rules, describe the language accepted by the given Turing machine:

$\begin{array}{l}\delta (q_0,0)=\{(q_0,1,R),(q_1,1,R)\};\\ \delta (q_1,1)=\{(q_2,0,L)\};\\ \delta (q_2,1)=\{(q_0,1,R)\};\\ \delta (q_1,B)=\{(q_f,B,R)\}.\end{array}$

Given two DFAs M1 and M2 over the same alphabet Σ, design a third DFA M3 such that M3 will accept the string w ∈ Σ* if it is accepted by both M1 and M2.

Differentiate between Moore and Mealy machines.

Design a DFA that accepts odd length binary strings.

How do you convert CFG to PDA? Explain.

Why do we need ε transition? Give the formal definition of PDA.

Describe abstract, decision and optimization problems.