FOR FREE CONTENT

Design a DFA for Language: “Start with ‘a’ and end with ‘a’”

∑ = {a, b}

 

Answer: 

 

L = {a, aa, aba, aabaa, …..}

Now one move is still left i.e. b moves for  q1.

If we use the back direction of b, q1 to q0 it creates a problem. Like the string ‘aabba’ is rejected, but it should be accepted. Because after we back b, it gets state q0 and then b, it goes to qt (Trap State) then for next a, it again goes to (Trap State). So it is rejected.

 

Note: if we have trap state in our DFA then carefully do the back direction for any input.

 

Then,

 

Regular Expression:  a (a+b)*a

 

Grammar:

S → aA

A → aA | bB | λ

B → bB | aA