STUPIDSID
1 (a)
Design a DFA to read strings mode up of letters 'CHARIOT' and recognize these strings that contains the word 'CAT' as a substring.
8 M
1 (b)
Draw DFA to accept the language L= { ω: ω has add number of } and followed by even number of 0's. Completely define DFA and transition function.
6 M
1 (c)
Convert the following NFA to its equivalent DFA.
6 M
2 (a)
Probe that if L=L(A) for some DFA, then there is a regular expression R such that L=L(R).
6 M
2 (b)
For the following DFA, obtain regular expression Rij(0) and Rij(1).
| States | Σ | |
| 0 | 1 | |
| → q1 | q2 | q1 |
| q2 | q3 | q1 |
| q3 | q3 | q2 |
9 M
2 (c)
Construct NFA for regular expression V=(01+10).
5 M
3 (a)
State and prove pumping Lemma for regular languages.
5 M
3 (b)
Show that L={An| u ≥ 0} is not regular.
5 M
3 (c)
Construct 0 minimum automation equivalent to given automation 'M' whose transition table given below.
| States | Input | |
| 0 | 1 | |
| →q0 | q0 | q3 |
| q1 | q2 | q5 |
| q2 | q3 | q4 |
| q3 | q0 | q5 |
| q4 | q0 | q6 |
| q5 | q1 | q4 |
| q6 | q1 | q3 |
10 M
4 (a)
What is grammar? Explain the classification of grammars with examples.
7 M
4 (b)
Obtain the grammar to generate the following languages.
i) L= {ω : na (ω) mod 2=0 where ω ∈ (a,b)*}
ii) L={ω : ω is a palindrome , where ω ∈ (a,b)*
iii) L=anb2n| u ≥ 1.
i) L= {ω : na (ω) mod 2=0 where ω ∈ (a,b)*}
ii) L={ω : ω is a palindrome , where ω ∈ (a,b)*
iii) L=anb2n| u ≥ 1.
6 M
4 (c)
Show that the following grammar is ambiguous:
S → a|Sa| bSS | Ssb | SbS.
S → a|Sa| bSS | Ssb | SbS.
7 M
5 (a)
Construct PDA for the language and simulate this PDA
L={aibjck | j=i+k,i,k≥0.
L={aibjck | j=i+k,i,k≥0.
10 M
5 (b)
Define PDA. Explain the language accepted by PDA.
5 M
5 (c)
Explain the PDA with two stocks.
5 M
6 (a)
Simplify the grammar by eliminating useless productions
S AB
A → a
B → C | b
C → D
D → E | bC.
E → d | Ab.
S AB
A → a
B → C | b
C → D
D → E | bC.
E → d | Ab.
6 M
6 (b)
Convert the following CFG and CNF.
S → aB | bA
A → a | aS | bAA
B → b | aS | aBB.
S → aB | bA
A → a | aS | bAA
B → b | aS | aBB.
6 M
6 (c)
Prove that context free language are closed under union, concatenation and star.
8 M
7 (a)
Explain the programming techniques for turning machine.
10 M
7 (b)
Construct a TM for L={ au bu cu | u ≥ 1}. Give the graphical representation for the obtained TM.
10 M
Explain the following
8 (a)
Post correspondence problem.
5 M
8 (b)
Recursively enumerable language.
5 M
8 (c)
Recursively language.
5 M
8 (d)
Universal language.
5 M
More question papers from Formal Languages and Automata Theory