10
1]

12
13

14

15

16

17

18
19

20

a)
b)

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

a)
b)
a)
b)

06000CS301122001

PART C
Answer all questions, each carries 3 marks.
Design a CFG to generate L = {a™"b"c"d™ | m, n > 0}

List two CFLs which cannot be accepted by a DPDA

Write the formal definition of PDA

1.1 = {x in {a,b} | x contains odd number of b’s} and L2 = {x in {2.9} | ೫
contains even number of b’s}. What is the union ೦೯1.1 and 7

PART D
Answer any two full questions, each carries 9 marks.
State and prove Pumping Lemma for Regular Languages

Design a PDA which accepts the language L ={ Wew® | where W is in (മ)
॥
Explain different steps involved in the simplification of a CFG
Explain two modes of language acceptability of ೩ PDA
PART E

Answer any four full questions, each carries 10 marks.
Prove that L ಎ {a"b"c” |n > 0} is not Context Free using Pumping Lemma

Design a CSG for L= {4 "८" |n > 0)

Design a TM which accepts palindromes over the alphabet {a,b}
Write and explain the instantaneous description of a Turing Machine
Design a TM to increment a binary number

Explain Universal TM

Prove that halting problem of TM is undecidable

Explain Chomsky’s classification of grammars

Write note on the language acceptability of LBA

What is recursively enumerable set?

Complement of a recursive language is recursive. Explain why?

Page 2 of 2

(3)
(3)
(3)
(3)

(9)
(9)

(5)
(4)

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