Computer Engineering (Semester 4)
TOTAL MARKS: 80
TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Assume data if required.
(4) Figures to the right indicate full marks.
1 (a) State and Prove the pumping lemma for the regular grammar.(5 marks)
1 (b) Explain different types of techniques for Turing Machine Construction. (5 marks)
1 (c) Compare and Contrast Mealy Machine and Moore Machine(5 marks)
1 (d) Prove that it is undecidable whether context free grammar is ambiguous.(5 marks)
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 marks)
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 marks)
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 marks)
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 marks)
4 (a)
Design a PDA to accept each of the following languages
i. {0n1m0n | m,n≥1}
ii. {0n1m0m0n | m,n≥1}(10 marks)
4 (b) Convert the grammar
s->0AA
A->0S|1S|0
to a PDA that accept same language by empty stack.(10 marks)
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 marks)
5 (b) Prove that L={<an|n is prime} is not context free.(10 marks)
6 (a) Design Turning Machine for the following language set of all strings of balanced paranthesis (10 marks)
6 (b) Convert the following grammar to Gribach normal form
S→AB1|0
A→00A|B
B→|A|(10 marks)
7 (a) Myhill-Nerode theorem.(5 marks)
7 (b) Post Correspondence Problem.(5 marks)
7 (c) Universal Turning Machine.(5 marks)
7 (d) The Classes P and NP. (5 marks)
and 3 others joined a min ago.
teamques10
★ 68k
sagarkolekar
★ 11k