MORE IN Theoretical Computer Science
MU Computer Engineering (Semester 4)
Theoretical Computer Science
May 2012
Total marks: --
Total time: --
INSTRUCTIONS
(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) 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
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.
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}
10 M
4 (b) Convert the grammar
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
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|
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