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 ?

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 )*)*

(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

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

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