MORE IN Theoretical Computer Science
MU Computer Engineering (Semester 4)
Theoretical Computer Science
December 2012
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

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 ?
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 )*)*
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".
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
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