3
$\begingroup$

I've converted an NFA to a DFA. But even after checking over it a few times, it still doesn't feel right. I'm sure this is trivial, but I'd like someone to give me an idea where I went totally wrong on this.

NFA:

NFA

DFA:

DFA

$\endgroup$
  • $\begingroup$ Why would you say it doesn't feel right? It does to me. $\endgroup$ – Untitled Sep 20 '13 at 3:01
  • $\begingroup$ You could use ony drawing tool to get nicer images (Libre Office Draw, GraphViz, LaTeX with TikZ, ...). At least you can crop and rotate the images properly, convert to grayscale and fiddle around with contrast and brightness. As for your question, there are algorithms to do this conversion; why do you doubt them? $\endgroup$ – Raphael Sep 20 '13 at 15:20
3
$\begingroup$

Well, of course you have to merge the two empty states and there should be two transitions $(\{q_5\}, a, \emptyset)$ and $(\{q_5\}, b, \emptyset)$ if you want a complete automaton, but otherwise, it looks right and I agree with Subhayan: both automata accept $ab^+ \cup ab^+a$.

$\endgroup$
  • $\begingroup$ I added $(\{q_5\}, a, \emptyset)$ and $(\{q_5\}, b, \emptyset)$ so it just merges with the $\emptyset$ closest to it. So there's still two $\emptyset$ on the graph. How wrong is that? It's really for convenience when drawing. $\endgroup$ – stackuser Sep 20 '13 at 15:54
  • $\begingroup$ There is nothing wrong as long as you know that these two empty states can be merged. What I mean is that you obtained an automaton with 5 states, not with 6 states. One can prove actually that it is the minimal automaton of your language. This would be the next exercise... $\endgroup$ – J.-E. Pin Sep 20 '13 at 16:06
2
$\begingroup$

Based on your constructions, it seems like both machines accept the same language, i.e. $ab^+ \cup ab^+a$.

$\endgroup$
  • 1
    $\begingroup$ Could you give an idea of how you reached that conclusion? $\endgroup$ – Luke Mathieson Sep 20 '13 at 4:19
  • $\begingroup$ i tried to "simulate the machines" independently, it seemed to me that the DFA and NFA both accepted languages that start with $a$, contains at-least one $b$ and also those (with the same conditions as prev and) that end with an $a$. Do you think I got it wrong somehow? $\endgroup$ – Subhayan Sep 20 '13 at 4:59
  • 1
    $\begingroup$ no, not at all, just trying to encourage the best answer possible :) $\endgroup$ – Luke Mathieson Sep 20 '13 at 9:19
  • $\begingroup$ phew :) ... although i should have made that explicit in the answer itself.. anyway, thanks to you we got that covered now. $\endgroup$ – Subhayan Sep 20 '13 at 9:27

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.