MU Theoretical Computer Science - May 2013 Exam Question Paper

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 = {aⁿb^maⁿ | 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 = {aⁿ bⁿ | 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

SPONSORED ADVERTISEMENTS