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⁽⁰⁾ and R_ij⁽¹⁾.

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ⁿ| u ≥ 0} is not regular. 8 marks

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

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ⁿb²ⁿ| 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ⁱb^jc^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 (b) Recursively enumerable language. 8 marks

8 (c) Recursively language. 8 marks

8 (d) Universal language. 8 marks