STUPIDSID
1(a)
What is finite automation? Give the finite automation M accepting (a,b)*(baaa).
5 M
1(b)
Explain Chomsky Hierarchy with languages used, forms of productions in grammars and accepting device.
5 M
1(c )
Differentiate Moore and Mealy machine.
5 M
1(d)
Give and explain ambiguous context free language.
5 M
2(a)
Design finite state machine to add 2 binary numbers of equal length.
10 M
2(b)
Give the rules for defining languages associated with any regular expression:Let, L1 = all words beginning with a L2 = all words ending with awhat is L1 intersection L2 ?
10 M
3(a)
Give the statement for pumping Lemma for regular languages
2 M
3(b)
Construct an NFA for
(i) (00 + 1) * (10)*
(ii) ((0 + 1)* 10 + (00)*(11 )*)*
(i) (00 + 1) * (10)*
(ii) ((0 + 1)* 10 + (00)*(11 )*)*
8 M
3(c)
Let G be the grammar
S ? aB | bA
A ? a | aS | bAA
B ? b | bS | aBB
Find the leftmost derivation, right most derivation and parse tree for the string "bbaaabbaba".
S ? aB | bA
A ? a | aS | bAA
B ? b | bS | aBB
Find the leftmost derivation, right most derivation and parse tree for the string "bbaaabbaba".
10 M
4(a)
What is TM? Give the power of TM over FSM. Explain undecidebility and incompleteness in Turing machine.
10 M
4(b)
Explain PDA and power of PDM. Also design the NPDA for the given CFG:
S ? aAA
A ? bS
A ? aS
S ? a
S ? aAA
A ? bS
A ? aS
S ? a
10 M
5(a)
Explain basic Complexity classes.
6 M
5(b)
Define NP-hard and NP-complete languages.
4 M
5(c)
Using pumping lemma, check whether anbn is regular or not.
10 M
6(a)
How regular expression is converted to DFA? Explain all rules with example.
10 M
6(b)
Construct a PDA accepting the language of Palindromes.
10 M
Write Short Notes on (any four) :-
7(a)
Myhill Nerode Theorem
5 M
7(b)
Universal TM
5 M
7(c)
Rice Theorem
5 M
7(d)
Closure property and decision algorithm for CFL.
5 M
7(e)
Application areas of RE, FA,PDA, CFG,TM.
5 M
More question papers from Theory of Computer Science