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.
| ? | 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)
Begin with the grammar:S?ABC|BaB
A?Aaa|bAc|AAA
B?BbB|A|d
C?CA|AC
D??
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??
i. Eliminate ? production.
ii. Eliminate unit production.
iii. Eliminate useless symbols.
iv. Put grammar in CNF.
14 M
5(b)
Prove that L ={an | n is prime} is not context free.
6 M
6(a)
Design Turning Machine for the following language "set of all strings of balanced parenthesis"
10 M
6(b)
Convert the following grammar to Gribach normal form
S?AB1|0
A?00A|B
B?1A|
S?AB1|0
A?00A|B
B?1A|
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 Theory of Computer Science