# Union of two automata

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?

• Just try to build one automaton for both. It isn't even hard to do. – vonbrand Mar 21 '13 at 17:38
• Constructing an NFA for the union is trivial, determinising and minimising is easy, if not trivial, with the algorithms you know from lecture. – 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:

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

• That's great! Thank you. Also, what program did you use to make that automaton? It would be great for submitting my work? – jsan Mar 21 '13 at 18:01
• @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. – Eric Mar 21 '13 at 18:03
• @jsan I'm afraid not. If we loop on state 2, the automaton will accept bb since state 2 is an accept state. – Eric Mar 21 '13 at 18:06
• @jsan use graphviz, it's great for rendering graphs and automata in particular. It's easy to learn. – saadtaame Mar 21 '13 at 18:16
• It isn't minimal. You can e.g. identify 3 and 4 ;) – vonbrand Mar 21 '13 at 22:17