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 a
what is L1 intersection L2 ?
Let, L1 = all words beginning with a
L2 = all words ending with a
what 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 Theoretical Computer Science