10

11

12

13

14

15

16

a)

b)

a)

b)

a)

b)

a)
b)

a)

b)
a)

E192010 Pages:3

| ऋऽ | ?3 [24

Construct regular expression corresponding to the following state diagram:

0,1
இண்டு டு
Design an e-NFA for the regular expression (0--1)*01
PART C

Answer all questions, each carries 3 marks.

Write the conditions for a pushdown automaton to be considered as
deterministic.
Which are the methods to accept a string in a PDA? Whether both type of
PDAs can define the same language. Justify your answer.
Convert the following grammar to Chomsky Normal Form.
S-> 0501151൦
Whether the following grammar is ambiguous?
E-> E+E] E*E|I
I-> O|1alb
PART 0

Answer any two full questions, each carries 9 marks.

Verify that the following languages is not regular:
(2 | n>0 }

Which of the following operations are closed under regular sets. Justify your
answer.

i) Complementation ii) Set difference iii) string reversal iv) Intersection
Give a CFG for the language N(M) where M ಎ ({p,q,r}, (0, 1}, {Z, Xo},
6, ۹0, Z, r) and 6 is given by (2, €» Xo) = {(q, ZXo)}, 50 ‏وه‎ Xo) = {(r, €)}, 50
+ 1, 2( = {(q, ZZ)}, ०(१. 0, ೫) = {(q, 9).

Find the Greibach normal form grammar equivalent to the following CFG:
S— AB
A—BS|1
B— 0
Design a PDA to accept the language {0°"1" | 1 > 1}.
Find a CFG without €-productions equivalent to the grammar defined by
ऽ — ABaC, ABC, B->b/ €, ൧/൦, Dd
PART E

Answer any four full questions, each carries 10 marks.

State Pumping lemma for CFLs. Write the applications of pumping lemma for
CFL s. ∙∙∙

Check whether L={a'b'c’ | i > 0} belong to CFL or not.

Discuss about Multitape Turing Machines. Explain informally how they can

Page 2 of 3

4.5

4.5

4.5

4.5

4.5

4.5

4.5
4.5