1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Just try to build one automaton for both. It isn't even hard to do. $\endgroup$
    – vonbrand
    Commented Mar 21, 2013 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
    Commented Mar 22, 2013 at 13:35

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
11
  • $\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
    Commented Mar 21, 2013 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$
    – Cat
    Commented Mar 21, 2013 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$
    – Cat
    Commented Mar 21, 2013 at 18:06
  • 3
    $\begingroup$ @jsan use graphviz, it's great for rendering graphs and automata in particular. It's easy to learn. $\endgroup$
    – mrk
    Commented Mar 21, 2013 at 18:16
  • 2
    $\begingroup$ It isn't minimal. You can e.g. identify 3 and 4 ;) $\endgroup$
    – vonbrand
    Commented Mar 21, 2013 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.