Question Paper: Formal Languages and Automata Theory : Question Paper Dec 2013 - Computer Science Engg. (Semester 5) | Visveswaraya Technological University (VTU)
0

## Formal Languages and Automata Theory - Dec 2013

### Computer Science Engg. (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) Mention the difference between DFA,NFA and ?-NFA.(6 marks) 1 (b) Design a DFA which accept set of all string of 0's and 1's beginning with a 1 that,when interpreted as a binary integer ,is a multiple of 5.For example strings 101,1010 and 1111 are in the language :0,100,0101 and 111 are not (6 marks) 1 (c) Convert the following NFA to DFA using construction method:

 δ 0 1 →p {p,q} {p} q φ {r} r {p,r} {q}

(8 marks) 2 (a) Consider the following ?-NFA:

Compuer the ?-closure of each state .
Give the set of all string of lenghth 3 or less accepted by the automation
Convert the automation to DFA.
 δ ∈ a b → {r} {q} {p,r} q φ {p} φ *r {p,q} {r} {p}

(8 marks)
2 (b) Give the regular expression for the following languages:
L={a n b m:n ?4,m ?2};
L={w:w?(0,1) and |w| mod 3=0}
(4 marks)
2 (c) mention the application of regular expression (2 marks) 2 (d) prove that every language defined by RE is also defined by some finite automataion(6 marks) 3 (a) State and prove that pumping lemma of regular languages (6 marks) 3 (b) Obatin the regular expression or distinguish ?Minimize the following DFA using table finite automation using state climatation method (4 marks) 3 (c) When two sates are equivalent or distingushable ?minimize the following DFA using table filling algorithm
 δ 0 1 →q1 q2 q3 q2 q3 q5 q3 q4 q3 q4 q3 q5 *q5 q2 q5

(10 marks)
4 (a) Decline CFG .Design a context free grammer for the language :
L={a i bj ck, where i=J+k.j,k?0}
L={0 n+21n:n ?1}
(8 marks)
4 (b) What is an ambigous grammer? Show that grammer shown below is ambigous
S?AB|aaB
A&rarr|a
B ?b
(6 marks)
4 (c) Consider the grammer
E?+EE/EE/-EE/x/y
Find the left most derivation ,right most derivation and parsetree for the string "+ * - xyxy.
(6 marks)
5 (a) Discuss the language accepted by a PDA .design to PDA to accept the following language L=0<suo>2n 1n n?1}.draw the transmistion diagram for the constructed PDA ,Also show the moves made by PDA for the string "000011"</suo>(14 marks) 5 (b) Convert the following grammer to PDA that accept the same by empty stack: S?aABB/aAA
A?aBB/a
B?bBB/a
C ?a
(6 marks)
6 (a) What are useless production ? Eliminate ? unit and unless production from following grammer
A?bA/Bba/aa
B ?aba/b/D ,
C ?CA/AC/B ,
D ?a /?
(10 marks)
6 (b) Define chomskey normal form .convert the following CFG to CNF
S ?aSb/ab /Aa
A ? aab
(6 marks)
6 (c) prove that the context free languages are closed under union(4 marks) 7 (a) Design a turing machine to accept the languages L={ww R:w?(a,b)*}.write its transition diagram .Also show the sequence of moves made by the TM for the string "aabbaa"(14 marks) 7 (b) Define turing machin .Explain with a diagram general structure of multiple turning machine(6 marks)

### Write short note on:

8 (a) Recursive language(5 marks) 8 (b) universal turing machine (5 marks) 8 (c) Post correspondance problem(5 marks) 8 (d) Application Of Context free grammer(5 marks)