MU Computer Engineering (Semester 4)
Theoretical Computer Science
May 2015
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) Differentiate between NFA and DFA.
5 M
1 (b) State and Explain closure properties of Context Free Language.
5 M
1 (c) Explain with an example the Chomsky hierarchy.
5 M
1 (d) Compare recursive and recursively enumerable language.
5 M

2 (a) Construct PDA accepting the language L={anbn |n>0}.
10 M
2 (b) Design minimized DFA for accepting strings ending with 100 over alphabet (0,1).
10 M

3 (a) Convert (0+ε)(10)*(ε+1) into NFA with e-moves and obtains DFA.
10 M
3 (b) Construct Turing machine that accepts the string over ?=(0,1) and convert every occurrence of 111 to 101.
10 M

4 (a) Convert following Grammar to CNF and GNF
S→ASB/a/bb
A→aSA/a
B→Sbs/bb
10 M

5 (a) Design Moore Machine to generate output A if string is ending with abb, B if string ending with aba and C otherwise over alphabet (a,b) and convert it to Mealy machine.
10 M
5 (b) Construct TM to check wellformed ness of parenthesis.
10 M

Write short notes on:
6 (a) Rice theorem
5 M
6 (b) Variants of Turing Machine.
5 M
6 (c) Applications of Regular Expression
5 M
6 (d) Difference between PDA and NPDA
5 M



More question papers from Theoretical Computer Science
SPONSORED ADVERTISEMENTS