MU Computer Engineering (Semester 4)
Theoretical Computer Science
May 2016
Total marks: --
Total time: --
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

1(a) Explain post correspondence problem.
5 M
1(b) Differentiate between NFA and DFA.
5 M
1(c) Show that language L = {0i | 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}* | N1 (x) > Nb (x)}. Na (x) > Nb (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
→ q0 {q0, q1} {q1} {}
q1 {q2} {q1, q2} {}
*q2 {q0} {q2} {q1}
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).
10 M
5(b) State and prove Rice's theorem.
10 M

6(a) Design a Tuning machine as an acceptor foe the language
{anbm | 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