1(a)
Explain post correspondence problem.

5 M

1(b)
Differentiate between NFA and DFA.

5 M

1(c)
Show that language L = {0

^{i}| i is prime number} is not regular
5 M

1(d)
Compare recursive and recursively enumerable languages.

5 M

2(a)
Design the DFA to accept all the binary strings over ∑={0, 1} that are beginning with 1 and having its decimal value multiple of 5.

10 M

2(b)
Design DPDA to accept language L = {x ∈ {1, b}* | N

_{1}(x) > N_{b}(x)}. N_{a}(x) > N_{b}(x) means number of a's are greater than number of b's in string x.
10 M

3(a)
Explain variations and equivalence of Turing machine.

10 M

3(b)
State and prove pumping lemma for context free languages.

10 M

4(a)
Design mealy machine to find out 2's complement of a binary number.

10 M

4(b)
Convert the following NFA to an equivalent DFA

State | a | b | ∈ |

→ q_{0} |
{q_{0},_{ }q_{1}} |
{q_{1}} |
{} |

q_{1} |
{q_{2}} |
{q_{1},_{ }q_{2}} |
{} |

*q_{2} |
{q_{0}} |
{q_{2}} |
{q_{1}} |

10 M

5(a)
Consider the following grammar G = (V, T, P, S), V = {S, X}, T = {a, b} and productions P are

S → aSb | aX

X → Xa | Sa | a

Convert this grammar in Greibach Normal Form (GNF).

S → aSb | aX

X → Xa | Sa | a

Convert this grammar in Greibach Normal Form (GNF).

10 M

5(b)
State and prove Rice's theorem.

10 M

6(a)
Design a Tuning machine as an acceptor foe the language

{a

{a

^{n}b^{m}| n , m ≥ 0 and m ≥ n}
10 M

6(b)
Design PDA to check even parentheses over ∑={0, 1}.

10 M

More question papers from Theoretical Computer Science