STUPIDSID
1 (a)
Define D.F.A. what are the different between D.F.A and N.F.A?
6 M
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 M
1 (c)
Define N.F.A and construct an N.F.A that accept the language 'aa*(a+b)
6 M
2 (a)
Define ?-NFA.Construct the &isin-NFA that accept 01(0+1)*.
6 M
2 (b)
Let R be a regular expression.then there exists a finite automaton A=(Q,? &delta,q0,F).
6 M
2 (c)
Convert the following ?-NFA to DFA
8 M
3 (a)
Sate and prove pumping lemma for the regular language.
7 M
3 (b)
Obatin the R.E from The following FA using elimination method
5 M
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 M
4 (a)
Consider the following grammer:
E?EE/E-E
E?E*E/E/E
E?(E)
E?a/b/c
Obatin the left most derivation for the String (a+b*c )
Obatin the right most derivation for the String (a+b)*c
E?EE/E-E
E?E*E/E/E
E?(E)
E?a/b/c
Obatin the left most derivation for the String (a+b*c )
Obatin the right most derivation for the String (a+b)*c
8 M
4 (b)
Prove that the following grammer is ambiguous ,using the string "ibtibtaea".
S?iCtS/iCtSeS/a
C ?b
S?iCtS/iCtSeS/a
C ?b
8 M
4 (c)
Discuss the various application of contaxt free grammer
4 M
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.
L={na(w)=nb(w)where n ?1}
Draw the transition diagram for PDA .Also ,show the moves made by aabbab.
12 M
5 (b)
Obtain the PDA for the following grammer: S?aSa/aa
?bSb/bb
?bSb/bb
8 M
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.
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 M
6 (b)
Obatin the following grammer in CNF:
S?OA/1B
A ?OAA/1S/1
B?!BB/OS/o
S?OA/1B
A ?OAA/1S/1
B?!BB/OS/o
10 M
7 (a)
Design a turing machine to accetp the following language L={on1n/n ?1}
Also show the sequence of moves mde by the TM for the string "00001111"
Also show the sequence of moves mde by the TM for the string "00001111"
14 M
7 (b)
Write a note on multitape turing machine and non-Detreministic turing machine
6 M
Write short notes on:
8 (a)
Post correspondance problem
5 M
8 (b)
Halting problem of TM
5 M
8 (c)
universal turing machine
5 M
8 (d)
Application Of R.E
5 M
More question papers from Formal Languages and Automata Theory