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

## Formal Languages and Automata Theory - Jun 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) Define D.F.A. what are the different between D.F.A and N.F.A?(6 marks) 1 (b) Consruct a D.F.A to accept String over {a,b} such that every book of length five conatin atleast two a's(8 marks) 1 (c) Define N.F.A and construct an N.F.A that accept the language 'aa(a+b)(6 marks) 2 (a) Define ?-NFA.Construct the &isin-NFA that accept 01(0+1).(6 marks) 2 (b) Let R be a regular expression.then there exists a finite automaton A=(Q,? &delta,q0,F).(6 marks) 2 (c)

Convert the following ?-NFA to DFA (8 marks) 3 (a) Sate and prove pumping lemma for the regular language.(7 marks) 3 (b) Obatin the R.E from The following FA using elimination method (5 marks) 3 (c) Minimize the following DFA using table filling algorithm

 State →A B (C) D E F G H 0 B G A C H C G G 1 F C C G F G E C

(8 marks) 4 (a) Consider the following grammer:
E?EE/E-E
E?EE/E/E
E?(E)
E?a/b/c
Obatin the left most derivation for the String (a+bc )
Obatin the right most derivation for the String (a+b)
c
(8 marks)
4 (b) Prove that the following grammer is ambiguous ,using the string "ibtibtaea".
S?iCtS/iCtSeS/a
C ?b
(8 marks)
4 (c) Discuss the various application of contaxt free grammer(4 marks) 5 (a) Define PDA.Obtain a PDA to accept the following language:
L={na(w)=nb(w)where n ?1}
Draw the transition diagram for PDA .Also ,show the moves made by aabbab.
(12 marks)
5 (b) Obtain the PDA for the following grammer: S?aSa/aa
?bSb/bb
(8 marks)
6 (a) What is an unit production? Begin with the grammar:
S→ABC|BaB
A→aA|BaC|aaa
B→bBb|a|D
D→ ε
Eliminate &epsilon- productions.
Eliminate any unit productions in the resulting grammar.
Eliminate any useless symbol in the resulting grammar.
(10 marks)
6 (b) Obatin the following grammer in CNF:
S?OA/1B
A ?OAA/1S/1
B?!BB/OS/o
(10 marks)
7 (a) Design a turing machine to accept the following language L={on1n/n ?1}
Also show the sequence of moves made by the TM for the string "00001111"
(14 marks)
7 (b) Write a note on multitape turing machine and non-Detreministic turing machine(6 marks)

### Write short notes on:

8 (a) Post correspondance problem(5 marks) 8 (b) Halting problem of TM(5 marks) 8 (c) universal turing machine (5 marks) 8 (d) Application Of R.E(5 marks)

 written 20 months ago by Team Ques10 ♦♦ 400