Question Paper: Formal Languages and Automata Theory Question Paper - June 2015 - Computer Science (Semester 5) - Visveswaraya Technological University (VTU)
0

## 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 Rij(0) and Rij(1).

<colgroup span="3" style="text-align: center;" width="85"> </colgroup>
 States Σ 0 1 → q1 q2 q1 q2 q3 q1 q3 q3 q2
8 marks

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

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

<colgroup span="3" style="text-align: center;" width="85"> </colgroup>
 States Input 0 1 →q0 q0 q3 q1 q2 q5 q2 q3 q4 q3 q0 q5 q4 q0 q6 q5 q1 q4 q6 q1 q3
8 marks

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= {ω : na (ω) mod 2=0 where ω ∈ (a,b)}
ii) L={ω : ω is a palindrome , where ω ∈ (a,b)

iii) L=anb2n| 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={aibjck | 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={ au bu cu | 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