00000CS301121901

6 a) State Myhill-Nerode theorem, Minimize the following DFA.

b) Find an equivalent ‏طے‎ ۲۸ for the following regular expression
(0 + 1)*011
7 ഒ) Convert the following e-NFA to NFA

7

b) Describe clearly the equivalent classes of the Canonical Myhill-Nerode relation

for the language of binary strings with second-last symbol as 0.
PART C
Answer all questions, each carries3 marks.
8 State the closure properties of regular sets.
9 Define context free grammar. Consider the following CFG
S—>aS|Sb |a |b

Prove by induction on the string length that no string in L(G) has ba as

substring.
10 Design a PDA to accept the set of strings with twice as many 0’s as 1’s.
11 List the decision problems related with type 3 Formalism.

PART 0
Answer any two full questions, each carries9 marks.
12 a) State pumping lemma for regular languages. Prove that the language L =

(८ | n> 0] is not regular.

b) Convert the following grammar into Chomsky normal form

5೨4981೮, 4௧49) 8 505/40)

(5)

(4)

(4)

(5)

(3)
(3)

(3)
(3)

(5)

(4)