10
11

12

13

14

15

16

17

18

19

20

a)
b)
a)
b)

a)
b)

a)
b)

00000CS301121902

Given that, the language {a”b" | n > 0} is not regular. Prove that the language {w
€ {a, b}* | w has equal number of ‘a’s and ‘b’s} is not regular, without using
Pumping Lemma.
Give a formal definition for NPDA.
Give a PDA which accepts the language {a"b" |n > 0} by empty stack
PART D
Answer any two full questions, each carries 9 marks.

Is the following language regular? Prove it.

(i) {w € {0, 1}* | the length of w is a prime number}

(11) L* (i.e., the Kleene closure of L) where L = (മ്‌ | where p is a prime

number }
Give a CFG with two productions for the language { a” | + > O}and convert it
into Chomsky Normal Form.
Prove that there is a PDA which accepts a language L by final state ifand only if
there is a PDA which accepts L by empty stack.
PART E
Answer any four full questions, each carries 10 marks.

State ‘Pumping Lemma for Context Free Languages.’
Prove that the language {0"/"2" | n > 0) is not a CFL.
Design a Turing Machine which accepts the set of all palindromes over {a, 0}
Show the computations done by the above machine when the input is ‘1001’ by
means of Instantaneous Descriptions (IDs).
Design a Turing Machine that multiplies two unary numbers, by first giving an
outline of the strategy of operation of the machine in English sentences.
Give the structure and explain the working of a Multi-tape Turing Machine
Give a formal definition for a Non-deterministic Turing Machine. Show an
example NDTM
Prove that if a language L is recursive, so is its complement.
Prove that if both a language L and its complement are recursively enumerable,
then L is recursive.

Prove that ‘Turing Machine Halting Problem’ is undecidable.

Page 2 of 2

(3)

(3)
(3)

(9)

(9)

(9)

(3)
(7)
(8)
(2)

(10)

(5)
(5)

(5)
(5)

(10)