13

14

15

16

17

18

19

20

i)

a)
b)
a)
b)

a)
b)
a)
b)
a)
b)
a)

b)

A5810 Pages: 2

Do the following:
Derive any two representative strings with minimum length 4 from following
context free grammar. G= ( {S,A,B},{a,b},P,S )
S> bA|aB
A> ^^ | 25 | 8
8-2 288 | 95 |b
Draw derivation tree corresponding to string aabbab with respect to
aforementioned grammar.
Prove the equivalence of push down automata and context free grammar.
PART E
Answer any four full questions, each carries 10 marks

State pumping Lemma for context free language

Define formally Turing machine Model.

Design Turing machine to accept language L={0"1"|n >=1}

Describe all instantaneous descriptions (ID) from initial ID 0101 to Final ID with
respect to constructed TM. Assume 40 as start state.

Design Turing machine to compute addition of two numbers. Assume unary
notation for number representation.

Describe all instantaneous descriptions (ID) from initial ID: qo010 to Final ID:
00 with respect to constructed Turing Machine.(assume qo as initial state.)
Explain the significance of universal Turing machine.

Compare and contrast recursive and recursively enumerable languages.

Prove that union of two recursive languages is recursive.

Explain the significance of halting problem.

Explain general notations for productions of each formal language from
Chomsky hierarchy.

Prove that complement of a recursive language is recursive.
೫ೇ ೫ मं ೫

Page 2 of 2

(9)

(9)

(5)
(5)
(6)
(4)

(6)
(4)
(5)
(5)
(5)
(5)
(5)

(5)