STUPIDSID
1(a)
State applications where Automata Theory is used.
5 M
1(b)
What are limitations of finite automata.
5 M
1(c)
Develop an NF A to accept stringd ending with 'aba' over {a, b}
5 M
1(d)
Explain with example equivalence between NFA &DFA.
5 M
2(a)
Consider the grammar G={S, A}, (0, 1) P, S}, where P consists of:
i) S→0AS|0 ii) A→S 1A |SS|10 Show the leftmost derivation for the input string '001100'. Is given G Ambiguous?
i) S→0AS|0 ii) A→S 1A |SS|10 Show the leftmost derivation for the input string '001100'. Is given G Ambiguous?
10 M
2(b)
Construct deterministic PDA to recognize an abbn, 0 over {a, b}
10 M
3(a)
Define Normal form and its types and Convert given grammar to CNF:
i) S→ bA |aB ii) A →bAA |aS| a iii) B → aBB |bS| b
i) S→ bA |aB ii) A →bAA |aS| a iii) B → aBB |bS| b
10 M
3(b)
Define CFG a construct a CFG for a2nbn
10 M
4(a)
Design mealy machine to accept all strings ending with aa or bb.
10 M
4(b)
Minimize given DFA-
!mage
!mage
10 M
5(a)
Develope ε-NFA to accept 0n 1n 2n, where n >=0 over {0, 1, 2}
5 M
5(b)
Define Halting problem.
5 M
5(c)
Give Regular Expressions for-
i) Binary strings containing atleast one 11 & atleast one 00
ii) Strings with even number of a's
iii) Strings in which third symbol from end is 'c' over {a, b, c}
i) Binary strings containing atleast one 11 & atleast one 00
ii) Strings with even number of a's
iii) Strings in which third symbol from end is 'c' over {a, b, c}
6 M
5(d)
Describe Regular Language for given Regular Expressions
i) (ab + ba)*
ii) 1 (0 +1) (0+1) (0 +1)* 0
i) (ab + ba)*
ii) 1 (0 +1) (0+1) (0 +1)* 0
4 M
6(a)
Write short note on - Chosmsky Hierarchy
7 M
6(b)
Explain Post correspondence problem.
7 M
6(c)
Explain Pumping Lemma for Regular Language.
6 M
More question papers from Automata Theory