STUPIDSID
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'
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 M
1 (b)
Define NFA"Convert the following NFA to its equivalent DFA [figure Q1.(b)]-
10 M
2 (a)
Consider the following ?NFA:
computer the ? -closure of each state
convert to DFA
computer the ? -closure of each state
convert to DFA
| ∈ | a | b | c | |
| → | φ | {p} | {q} | {r} |
| q | {p} | {q} | {r} | φ |
| *r | {q} | {r} | φ | {p} |
8 M
2 (b)
Define Regular expression. Convert the following automation to a regular expression using state elirnination technique.
10 M
2 (c)
Convert the regular expression (0 + 1). | (0 +1) to anNFA
4 M
3 (a)
State and prove pumping lemma for regular languages
10 M
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 M
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
L={0 n |n ?1}
L={string /of a 's and b's with equal number grammer is ambigues
6 M
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.
E -+E+E E-E I E *E I E/E | (E) | a where whereE is the start symbol. Find the unambiguous grammar.
10 M
4 (c)
Discu ss the applications of CFG
4 M
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 M
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 ??
A?ABB|a
B ?bBB|A
C ??
10 M
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.
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 M
6 (b)
What is CNF and GNF? Obtain the following grammar in CNF S ?aBa|abba
A ? ab|AA
B ? aB|a
A ? ab|AA
B ? aB|a
10 M
7 (a)
Define'a turing machine and explain with neat diagram, the working of a basic turing machine
6 M
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 M
Write short note on:
8 (a)
Multipe turing machine
5 M
8 (b)
Post's correspondence problem
5 M
8 (c)
Pumping lemma for CFL
5 M
8 (d)
Recursive languages
5 M
More question papers from Formal Languages and Automata Theory