STUPIDSID
1 (a)
State and Prove the pumping lemma for the regular grammar.
5 M
1 (b)
Explain different types of techniques for Turing Machine Construction.
5 M
1 (c)
Compare and Contrast Mealy Machine and Moore Machine
5 M
1 (d)
Prove that it is undecidable whether context free grammar is ambiguous.
5 M
2 (a)
Write a regular expression for the following languages:
i. The set of all the strings such that the number of 0's is odd.
ii. The set of all the strings that do not contain 1101
i. The set of all the strings such that the number of 0's is odd.
ii. The set of all the strings that do not contain 1101
10 M
2 (b)
Convert the following NFA to DFA
p is the initial state r and s it the final state.
p is the initial state r and s it the final state.
| δ | 0 | 1 |
| →p | {p,r} | {q} |
| q | {r,s} | {p} |
| r* | {p,s} | {r} |
| s* | {q,r} | {} |
10 M
3 (a)
Show that every regular language is a context free language.
HINT: Construct a CFG by induction on the number of operators in the regular expression.
HINT: Construct a CFG by induction on the number of operators in the regular expression.
10 M
3 (b)
A palindrome is a string that equals its own reverse, such as 0110 or 1011101. Use pumping lemma to show that set of palindromes is not regular language.
10 M
4 (a)
Design a PDA to accept each of the following languages
i. {0n1m0n | m,n≥1}
ii. {0n1m0m0n | m,n≥1}
i. {0n1m0n | m,n≥1}
ii. {0n1m0m0n | m,n≥1}
10 M
4 (b)
Convert the grammar
s->0AA
A->0S|1S|0
to a PDA that accept same language by empty stack.
s->0AA
A->0S|1S|0
to a PDA that accept same language by empty stack.
10 M
5 (a)
S->ABC|BaB
A->Aaa|bAc|AAA
B->BbB|A|d
C->CA|AC
D->E
i. Eliminate ∈ production
ii. Eliminate unit production
iii. Eliminate useless symbols
iv. Put grammar in CNF
A->Aaa|bAc|AAA
B->BbB|A|d
C->CA|AC
D->E
i. Eliminate ∈ production
ii. Eliminate unit production
iii. Eliminate useless symbols
iv. Put grammar in CNF
10 M
5 (b)
Prove that L={<an|n is prime} is not context free.
10 M
6 (a)
Design Turning Machine for the following language set of all strings of balanced paranthesis
10 M
6 (b)
Convert the following grammar to Gribach normal form
S→AB1|0
A→00A|B
B→|A|
S→AB1|0
A→00A|B
B→|A|
10 M
7 (a)
Myhill-Nerode theorem.
5 M
7 (b)
Post Correspondence Problem.
5 M
7 (c)
Universal Turning Machine.
5 M
7 (d)
The Classes P and NP.
5 M
More question papers from Theoretical Computer Science