1 (a)
Define the following terms:

(i) Undecidability

(ii) Unrestricted Grammer

(iii) Pumping Lemma

(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.

(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

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

(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

^{n}b^{m}a^{n}| 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

^{n}b^{n}| 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