0
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ You would guess correctly. But you can then simplify further. There is an algebra on regular expression that allows you to transform them as you do with arithmetic expressions. For example , if $e$ is a regular expression, $(e^*)^*=e^*$, or $e(e'+e'')=ee'+ee''$. But your DFA seems incorrect. It looks like you do not want $b$ in any word of your language. Or is it intended only for the part of the expression you simplified? $\endgroup$ – babou May 22 '15 at 23:32
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Your second transformation is wrong. $(a+b)^*$ accepts the word $\sigma=a$ but $(a^*b)^*$ does not accept $\sigma$. $\endgroup$ – Renato Sanhueza May 24 '15 at 3:42
  • $\begingroup$ Oh.. My mistake.. I was in Hurry.. Editing it.. $\endgroup$ – user388229 May 24 '15 at 3:51
1
$\begingroup$

I recommend you first try to understand the language denoted by the regular expression. Once done this can make it easier to build the DFA directly . If you can not think of how to build the DFA you can always turn your regular expression into an NFA and then the NFA into a DFA(Convert regular expression to DFA).

The strings denoted by your regular expression are:

Empty string or a concatenation of strings formed by a chain of zero or more $a's$ followed by a $b$. This mean that your initial state should be a final state too and a word in this language "always"(except $\epsilon$) finish with a letter $b$ so your DFA can't transition to a final state consuming a letter $a$. I hope those hints can help you to generate your DFA directly.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.