MORE IN Theoretical Computer Science
MU Computer Engineering (Semester 4)
Theoretical Computer Science
May 2013
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) Define the following terms:
(i) Undecidability
(ii) Unrestricted Grammer
(iii) Pumping Lemma
5 M
1 (b) Define TM and give its variants.
5 M
1 (c) Explain Chomsky hierarchy for formal languages.
5 M
1 (d) Give the closure properties of regular languages.
5 M

2 (a) (i) What is ambiguous CFG? Give one example.
(ii) What is Myhill-Nerode theorem? Explain necessity of it.
10 M
2 (b) Let G be the grammar, find the leftmost derivation, rightmost derivation and parse tree for the string 00110101
S → 0B/1A
A → 0/0S/1AA
B → 1/1S/0BB
10 M

3 (a) Explain CNF and GNF with example.
10 M
3 (b) Give the formal definition of RE and Design DFA corresponding the regular expression (a+b)*aba( a + b )*
5 M
3 (c) Using pumping lemma prove L = {anbn | n?1} is not regular or not.
5 M

4 (a) Write NFA for accepting (a+bb)*(ba*+ ∈)
10 M
4 (b) Explain DPDA and NPDA with languages of them.
10 M

5 (a) Find the languages defined by the following grammar:
(i) S→OA/IC
A→OS/IB/∈
B→1A/OC
C→OB/1S
(ii) S→OA/IC
A→OS/IB
B→OC/IB/∈
C→OB/IS
10 M
5 (b) Construct PDA of accepting the following language L = {anbman | m,n>=1}
10 M

6 (a) Differentiate between Moore and Mealy machine with proper example and usage. Carry out comparison of Moore MIC to Mealy MIC.
10 M
6 (b) Design a Turing Machine to accept the language L = {an bn | n>=1}
10 M

Write short notes on (any four)
7 (a) Recursive and recursively enumerable languages.
5 M
7 (b) Intractable Problems
5 M
7 (c) Simplification of CFGs
5 M
7 (d) Decision properties of regular languages.
5 M
7 (e) Rice Theorem
5 M

More question papers from Theoretical Computer Science