I've broken down the expression into two simpler DFAs but right now I'm stuck.

enter image description here

I don't know what to do with the expression a*, my solution currently (as presented above) is a NFA, not DFA.

  • 1
    $\begingroup$ Tip: it's a lot easier to read DFAs if you use arrows for the transitions! $\endgroup$
    – Draconis
    Jun 11 '19 at 3:17
  • 1
    $\begingroup$ 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. $\endgroup$
    – frabala
    Jun 11 '19 at 7:22
  • $\begingroup$ 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. $\endgroup$
    – John L.
    Jun 11 '19 at 13:30
  • $\begingroup$ It's worth noting that your NFA accepts $aaab$, which it shouldn't. $\endgroup$ 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)^*$.

The correct way to combine two DFAs so as to produce the union of their languages is to construct the product automaton of them, defining the new final states appropriately. Please check this question and answer for details.

For the current case, we can use more states in the DFA so that it remembers more about the input string and it is deterministic enough to stipulate each transition.

$$\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.


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.