FLAT imp qns(UNIT1 to UNIT4)

1. Design DFA for the following languages shown below Z= {a,b}

a) L= {w/w does not contain the substring ab}

b) L= {w/w contains neither the substring ab nor ba}

c) L= {w/w is any string that doesn’t contain exactly two a’s}

b) L= {w/w is any string except a and b}

2. For the following NFA with € moves convert it into an NFA without € moves and show that NFA with € moves accept the same language as shown in figure.

3.construct NFA for the following regular expression.

a) 0+10^*+01^* 0

b) (0+1)^* (01+110)

4. Define the following and give examples.

a) Regular grammar  b) Context Free Grammar c) Derivation tree

d) Sentential form e) Rightmost and Leftmost derivation of strings

5.Explain the conversation steps of NFA without €  to NFA with € ?

6.Explain Moore and Mealy Machine in detail with an example?