[Solved]: Draw a DFA that accepts ((aa*)*b)*

Problem Detail: 

A homework question asks me to a draw a DFA for the regular expression

$((aa^*)^*b)^*$

I'm having trouble with this because I'm not sure how to express the idea of $a$ followed by $0$ or many $a$'s many times, in terms of a DFA.

I would guess it that $(aa^*)^*$ should be the same thing as $\lambda + a^*$ but I'm not sure if I can formally say that. If I could, it would make my DFA simply

Asked By : CodyBugstein

Answered By : user388229

Edited:

• (a* a)* can be change to a*
• Now we have (a* b)*
• i.e. If nothing comes then, we have to be at final state. If b comes then, we have to be at final state. But if a comes then, sequence of a followed by single b is accepted.

DFA for this will be:

M=({q0,q1}, {a,b}, ∆, q0, {q0})

Where,

q0= initial as well as final state

And ∆: ∆(q0, b)=q0 ∆(q0, a)=q1 ∆(q1, b)=q0 ∆(q1, a)=q1

Explanation: As q0 is initial as well as final, then, epsilon and b is accepted. If a comes then, it will be followed be a b.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42883