Union of two automata

Problem Detail: 

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?

Asked By : jsan

Answered By : Eric

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.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10684