STUPIDSID
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).
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}
{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