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

## Formal Languages and Automata Theory - Jun 2014

### 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) Write the DFA for the following languages over ?{a,b}
The set of all strings ending with a&b
the set of all strings not containing the substring aab.
Set'of all strings with exactly three consecutive a'
(10 marks)
1 (b) Define NFA"Convert the following NFA to its equivalent DFA [figure Q1.(b)]- (10 marks) 2 (a) Consider the following ?NFA:
computer the ? -closure of each state
convert to DFA

 ∈ a b c → φ {p} {q} {r} q {p} {q} {r} φ r {q} {r} φ {p}

(8 marks) 2 (b) Define Regular expression. Convert the following automation to a regular expression using state elirnination technique. (10 marks) 2 (c) Convert the regular expression (0 + 1). | (0 +1) to anNFA(4 marks) 3 (a) State and prove pumping lemma for regular languages(10 marks) 3 (b) Define distinguishable and indistinguishable states.Minimize the following DFA using table filling algorithm
 0 1 A B F C G C C A C D C G E H F F C G G G E H G C

3

(10 marks)
4 (a) Define CFG. Write CFG for the following languages
L={0 n |n ?1}
L={string /of a 's and b's with equal number grammer is ambigues
(6 marks)
4 (b) What is an ambiguous grammar? Show that the following grammar is ambiguous.
E -+E+E E-E I E *E I E/E | (E) | a where whereE is the start symbol. Find the unambiguous grammar.
(10 marks)
4 (c) Discu ss the applications of CFG(4 marks) 5 (a) Define PDA. Construct PDA that accepts the language L={wwR|w?(a+b+ and WR is the reversal of {w} .write ID's for the string aaabbbaa.(10 marks) 5 (b) Convert the following CFG to PDA and give the procedure for the same. S ?aABB|aAA
A?ABB|a
B ?bBB|A
C ??
(10 marks)
6 (a) consider the following CFG
S ?aABB|aAA
A ?aBB|a
B ?bBB|A
C ? a
Shat are useless symbois?(ii) Eliminate e-productions unit productions and useless productions from the grammar.
(10 marks)
6 (b) What is CNF and GNF? Obtain the following grammar in CNF S ?aBa|abba
A ? ab|AA
B ? aB|a
(10 marks)
7 (a) Define'a turing machine and explain with neat diagram, the working of a basic turing machine(6 marks) 7 (b) Design a turing machine to accept the set of all palindromes over {a.b} *. iAlso, indicate the movesmade by turing machinefor the string ab(14 marks)

### Write short note on:

8 (a) Multipe turing machine(5 marks) 8 (b) Post's correspondence problem(5 marks) 8 (c) Pumping lemma for CFL(5 marks) 8 (d) Recursive languages(5 marks)