## Theoretical Computer Science - May 2012

### 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} |
{} |

**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)