STUPIDSID
Solve any five.
1 (a)
Explain if the following machine M is a DFA? Is it NFA? Write formally a definition for this M.
4 M
1 (b)
Design moore machine to convert each occurrence of 100 to 101.
3 M
1 (c)
Write a CFG to generate strings Starting and ending with different letter over the ∑={a, b}
3 M
1 (d)
What is Multi-Tape Turing Machine.
3 M
1 (e)
Difference between FA and PDA.
4 M
1 (f)
Give a regular expression for the language over the alphabet ∑={a, b} containing at most two a's.
3 M
2 (a)
Construct a minimal DFA which accepts L={anbmc1|n,mm|>=O}
5 M
2 (b)
State and explain Turing Machine Formalism 5.
5 M
2 (c)
If L(r)= {aaa, aab, aba, abb, baa, bab, bba, bbb}, find the regular expression r which represents L(r).
5 M
2 (d)
Explain Chomsky Hierarchy.
5 M
3 (a)
Construct a TM for accepting palindromes.
10 M
3 (b)
Design PDA For recognizing L={ambncm+n| m,n>=1}.
10 M
4 (a)
Convert the following grammer to Chomsky Normal Form. Show all the relevant Steps briefly.
S→bA| aB
A→ bAA|aS|a
B→aBB|bs|b
S→bA| aB
A→ bAA|aS|a
B→aBB|bs|b
10 M
4 (b)
Convert the followng Grammer G to GNF.
G={(A1, A2, A3), (a, b), (P, A1}
Where, P consist of the Following Productions:
A1→A2A3
A2→A3A1|b
A3→A1A2|a
G={(A1, A2, A3), (a, b), (P, A1}
Where, P consist of the Following Productions:
A1→A2A3
A2→A3A1|b
A3→A1A2|a
10 M
5 (a)
State and Prove pumping lemma for regular languages and prove that following language is regular or not
L={anbnI n>=1}
L={anbnI n>=1}
10 M
5 (b)
Construct NFA, DFA for the regular Expression R=ab(a+b)+abb. Obtain minimized DFA.
10 M
Write short notes on (any two).
7 (a)
Simplification of CFG.
10 M
7 (b)
Recursive and Recursively enumerable languages.
10 M
7 (c)
Universal TM
10 M
7 (d)
Halting Problem
10 M
More question papers from Automata Theory