Question

Question 5. Let Σ = {a, b}, and consider the language

L = {a n : n is even} ∪ {b n : n is odd}.

Draw a graph representing a DFA (not NFA) that accepts this language.

Question 6. Give a brief description of the language generated by the following production rules.

S → abc

S → aXbc

Xb → bX

Xc → Ybcc

bY → Yb

aY → aa

aY → aaX

Answer 1

Ans 5 :

L = {a n : n is even} ∪ {b n : n is odd}.

In the language given above we can see that it will contain either all a's as even of all b's as odd.

So, starting from the initial state q0 we can either to the way in which even number of a's are found or where the odd number of b's are found. The DFA for such a language is given below.