STUPIDSID
1 (a)
Mention the difference between DFA,NFA and ?-NFA.
6 M
1 (b)
Design a DFA which accept set of all string of 0's and 1's beginning with a 1 that,when interpreted as a binary integer ,is a multiple of 5.For example strings 101,1010 and 1111 are in the language :0,100,0101 and 111 are not
6 M
1 (c)
Convert the following NFA to DFA using construction method:
| δ | 0 | 1 |
| →p | {p,q} | {p} |
| q | φ | {r} |
| *r | {p,r} | {q} |
8 M
2 (a)
Consider the following ?-NFA:
Compuer the ?-closure of each state .
Give the set of all string of lenghth 3 or less accepted by the automation
Convert the automation to DFA.
Compuer the ?-closure of each state .
Give the set of all string of lenghth 3 or less accepted by the automation
Convert the automation to DFA.
| δ | ∈ | a | b |
| → | {r} | {q} | {p,r} |
| q | φ | {p} | φ |
| *r | {p,q} | {r} | {p} |
8 M
2 (b)
Give the regular expression for the following languages:
L={a n b m:n ?4,m ?2};
L={w:w?(0,1)* and |w| mod 3=0}
L={a n b m:n ?4,m ?2};
L={w:w?(0,1)* and |w| mod 3=0}
4 M
2 (c)
mention the application of regular expression
2 M
2 (d)
prove that every language defined by RE is also defined by some finite automataion
6 M
3 (a)
State and prove that pumping lemma of regular languages
6 M
3 (b)
Obatin the regular expression or distinguish ?Minimize the following DFA using table finite automation using state climatation method
4 M
3 (c)
When two sates are equivalent or distingushable ?minimize the following DFA using table filling algorithm
| δ | 0 | 1 |
| →q1 | q2 | q3 |
| q2 | q3 | q5 |
| *q3 | q4 | q3 |
| q4 | q3 | q5 |
| *q5 | q2 | q5 |
10 M
4 (a)
Decline CFG .Design a context free grammer for the language :
L={a i bj ck, where i=J+k.j,k?0}
L={0 n+21n:n ?1}
L={a i bj ck, where i=J+k.j,k?0}
L={0 n+21n:n ?1}
8 M
4 (b)
What is an ambigous grammer? Show that grammer shown below is ambigous
S?AB|aaB
A&rarr|a
B ?b
S?AB|aaB
A&rarr|a
B ?b
6 M
4 (c)
Consider the grammer
E?+EE/*EE/-EE/x/y
Find the left most derivation ,right most derivation and parsetree for the string "+ * - xyxy.
E?+EE/*EE/-EE/x/y
Find the left most derivation ,right most derivation and parsetree for the string "+ * - xyxy.
6 M
5 (a)
Discuss the language accepted by a PDA .design to PDA to accept the following language L=02n 1n n?1}.draw the transmistion diagram for the constructed PDA ,Also show the moves made by PDA for the string "000011"
14 M
5 (b)
Convert the following grammer to PDA that accept the same by empty stack: S?aABB/aAA
A?aBB/a
B?bBB/a
C ?a
A?aBB/a
B?bBB/a
C ?a
6 M
6 (a)
What are useless production ? Eliminate ? unit and unless production from following grammer
A?bA/Bba/aa
B ?aba/b/D ,
C ?CA/AC/B ,
D ?a /?
A?bA/Bba/aa
B ?aba/b/D ,
C ?CA/AC/B ,
D ?a /?
10 M
6 (b)
Define chomskey normal form .convert the following CFG to CNF
S ?aSb/ab /Aa
A ? aab
S ?aSb/ab /Aa
A ? aab
6 M
6 (c)
prove that the context free languages are closed under union
4 M
7 (a)
Design a turing machine to accept the languages L={ww R:w?(a,b)*}.write its transition diagram .Also show the sequence of moves made by the TM for the string "aabbaa"
14 M
7 (b)
Define turing machin .Explain with a diagram general structure of multiple turning machine
6 M
Write short note on:
8 (a)
Recursive language
5 M
8 (b)
universal turing machine
5 M
8 (c)
Post correspondance problem
5 M
8 (d)
Application Of Context free grammer
5 M
More question papers from Formal Languages and Automata Theory