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

9views

written 8.1 years ago by

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

(10 marks) 4 (a) Define CFG. Write CFG for the following languages
L={0 ⁿ |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={ww^R|w?(a+b+ and W^R 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)

ADD COMMENT EDIT