# Construct a DFA from the regular expression (a)*+(aab)*

I've broken down the expression into two simpler DFAs but right now I'm stuck. I don't know what to do with the expression a*, my solution currently (as presented above) is a NFA, not DFA.

• Tip: it's a lot easier to read DFAs if you use arrows for the transitions! – Draconis Jun 11 '19 at 3:17
• The idea of combining the two smaller DFAs is right, but indeed the resulting automaton is an NFA. You should look for material that explains how to convert NFAs to equivalent DFAs. – frabala Jun 11 '19 at 7:22
• Instead of $L\in a^*$, it is much better to write $L= a^*$ as we abuse a regular expression for the language it expresses by convention. – John L. Jun 11 '19 at 13:30
• It's worth noting that your NFA accepts $aaab$, which it shouldn't. – Rick Decker Jun 12 '19 at 15:35

The approach of combining two smaller DFAs is right. However, it is not correct to superimpose one DFA on another simply. For example, your combined DFA accepts $$aaab$$, which is not included in $$a^*+(aab)^*$$.
\begin{aligned} q_0&: \text{for the empty string}.\\ q_{a}&: \text{for string }a.\\ q_{aa}&: \text{for string }aa.\\ q_{aaaa^*}&: \text{for strings } aaa, aaaa, \cdots.\\ q_{aab(aab)^*}&: \text{for strings } aab, aabaab, \cdots.\\ q_{aab(aab)^*a}&: \text{for strings } aaba, aabaaba, \cdots.\\ q_{aab(aab)^*aa}&: \text{for strings } aabaa, aabaabaa, \cdots.\\ q_{\text{reject}}&: \text{for all other strings.}\\ \end{aligned}
$$q_0$$ is the initial state. $$q_0, q_{a}, q_{aa}, q_{aaaa^*}$$ and $$q_{aab(aab)^*}$$ are accept states. $$q_{reject}$$ is a dead state.