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

ignougroup
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 Simple DFA

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