I need to find a minimal DFA given the following information:

$ \{a^nb : n\geq 0\} \cup \{b^na: n \geq 1\}$

Now, maybe I'm not seeing this properly, but I don't see how this is possible: the first one will take 0 or more a's followed by one b, whereas the second one will take a 1 or more b's followed by one a.

Drawing the combined automata only brought me to trap states. Any suggestions?

  • 2
    $\begingroup$ Just try to build one automaton for both. It isn't even hard to do. $\endgroup$ – vonbrand Mar 21 '13 at 17:38
  • $\begingroup$ Constructing an NFA for the union is trivial, determinising and minimising is easy, if not trivial, with the algorithms you know from lecture. $\endgroup$ – Raphael Mar 22 '13 at 13:35

As @vonbrand suggested, using one automata (without attempting to combine them) is sufficient. Combining them will prove to be more work than it's worth.

Basically, here's the idea:

  • If you get an $a$, begin looping on $a^nb$. If you get a $b$ after this, accept. But anything further goes to the trash can.
  • If you get a $b$, accept for $a^0b$. If you get another $b$, you can then loop on $b$ under $b^na$. At any point in the loop, if you get an $a$, accept. But if you get anything after that $a$, go to the trash can.

Here is a textual representation (t is the "trash can" or trap state; + represents an accept state).

  | 0   | 1   | 2+  | 3+  | 4+  | 5
a | 1   | 1   | 4   | t   | t   | 4
b | 2   | 3   | 5   | t   | t   | 5

And here is a generated visual version:

enter image description here

(I'm not 100% sure this is minimal, but if it's not, it's a good exercise.)

| cite | improve this answer | |
  • $\begingroup$ That's great! Thank you. Also, what program did you use to make that automaton? It would be great for submitting my work? $\endgroup$ – jsan Mar 21 '13 at 18:01
  • 1
    $\begingroup$ @jsan I found a website called HackingOff that has some visual representation generators. They're in SVG, though, so you may have to use a screenshot or something like PhotoShop to get the image to a usable format. $\endgroup$ – Eric Mar 21 '13 at 18:03
  • 2
    $\begingroup$ @jsan I'm afraid not. If we loop on state 2, the automaton will accept bb since state 2 is an accept state. $\endgroup$ – Eric Mar 21 '13 at 18:06
  • 3
    $\begingroup$ @jsan use graphviz, it's great for rendering graphs and automata in particular. It's easy to learn. $\endgroup$ – saadtaame Mar 21 '13 at 18:16
  • 2
    $\begingroup$ It isn't minimal. You can e.g. identify 3 and 4 ;) $\endgroup$ – vonbrand Mar 21 '13 at 22:17

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.