## Formal Languages and Automata Theory - June 2015

### VTU Computer Science (Semester 5)

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)** Design a DFA to read strings mode up of letters 'CHARIOT' and recognize these strings that contains the word 'CAT' as a substring.
8 marks

**1 (b)** Draw DFA to accept the language L= { ω: ω has add number of } and followed by even number of 0's. Completely define DFA and transition function.
8 marks

**1 (c)** Convert the following NFA to its equivalent DFA.
8 marks

**2 (a)** Probe that if L=L(A) for some DFA, then there is a regular expression R such that L=L(R).
8 marks

**2 (b)** For the following DFA, obtain regular expression R_{ij}^{(0)} and R_{ij}^{(1)}.

States | Σ | |

0 | 1 | |

→ q_{1} |
q_{2} |
q_{1} |

q_{2} |
q_{3} |
q_{1} |

q_{3} |
q_{3} |
q_{2} |

**2 (c)** Construct NFA for regular expression V=(01+10).
8 marks

**3 (a)** State and prove pumping Lemma for regular languages.
8 marks

**3 (b)** Show that L={A^{n}| u ≥ 0} is not regular.
8 marks

**3 (c)** Construct 0 minimum automation equivalent to given automation 'M' whose transition table given below.

States | Input | |

0 | 1 | |

→q_{0} |
q_{0} |
q_{3} |

q_{1} |
q_{2} |
q_{5} |

q_{2} |
q_{3} |
q_{4} |

q_{3} |
q_{0} |
q_{5} |

q_{4} |
q_{0} |
q_{6} |

q_{5} |
q_{1} |
q_{4} |

q_{6} |
q_{1} |
q_{3} |

**4 (a)** What is grammar? Explain the classification of grammars with examples.
8 marks

**4 (b)** Obtain the grammar to generate the following languages.

i) L= {ω : n_{a} (ω) mod 2=0 where ω ∈ (a,b)*} ii) L={ω : ω is a palindrome , where ω ∈ (a,b)*

iii) L=a

^{n}b

^{2n}| u ≥ 1. 8 marks

**4 (c)** Show that the following grammar is ambiguous:

S → a|Sa| bSS | Ssb | SbS.
8 marks

**5 (a)** Construct PDA for the language and simulate this PDA

L={a^{i}b^{j}c^{k} | j=i+k,i,k≥0.
8 marks

**5 (b)** Define PDA. Explain the language accepted by PDA.
8 marks

**5 (c)** Explain the PDA with two stocks.
8 marks

**6 (a)** Simplify the grammar by eliminating useless productions

S AB

A → a

B → C | b

C → D

D → E | bC.

E → d | Ab.
8 marks

**6 (b)** Convert the following CFG and CNF.

S → aB | bA

A → a | aS | bAA

B → b | aS | aBB.
8 marks

**6 (c)** Prove that context free language are closed under union, concatenation and star.
8 marks

**7 (a)** Explain the programming techniques for turning machine.
8 marks

**7 (b)** Construct a TM for L={ a^{u} b^{u} c^{u} | u ≥ 1}. Give the graphical representation for the obtained TM.
8 marks

### Explain the following

**8 (a)**Post correspondence problem. 8 marks

**8 (b)** Recursively enumerable language.
8 marks

**8 (c)** Recursively language.
8 marks

**8 (d)** Universal language.
8 marks