**1 Answer**

written 6.9 years ago by |

## Theory of Computer Science - May 2012

### Computer Engineering (Semester 5)

TOTAL MARKS: 100

TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.

(2) Attempt any **four** from the remaining questions.

(3) Assume data wherever 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)**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.

(14 marks)

**5(b)**Prove that L ={a

^{n}| n is prime} is not context free.(6 marks)

**6(a)**Design Turning Machine for the following language "set of all strings of balanced parenthesis"(10 marks)

**6(b)**Convert the following grammar to Gribach normal form

S?AB1|0

A?00A|B

B?1A|(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)