3
$\begingroup$

I am learning about finite automata for the first time. I am having trouble understanding the purpose of ε-transitions in an NFA, which seem to be crucial to counting the number of states in an NFA and therefore an equivalent DFA.

Here is an example question that confuses me: What is the minimum number of states a DFA recognizing the language of a(bc)*d can have?

To answer this question, I first drew this NFA (dashed line indicates acceptance):

enter image description here

Because I think the above NFA is already a DFA, I thought the answer was "5".

However, the correct NFA and equivalent DFA look like this:

enter image description here

Which means the answer is "4". I understand why these are correct. But, I have some questions:

1) Is my original drawing actually an NFA? If not, why?

2) If the original drawing is an NFA, does it describe the language a(bc)*d? If not, why?

3) If the original drawing is an NFA that describes the language a(bc)*d, is it also a DFA? If not, why?

4) If the original drawing is an NFA and DFA that describes the language a(bc)*d, why should I have known to draw the NFA with ε-transitions instead?

Improve this question
$\endgroup$
3
  • $\begingroup$ I realize my original drawing has an unnecessary state. But, my questions still stand. $\endgroup$
    – justAnotherGuy
    Jan 31, 2016 at 9:04
  • $\begingroup$ Look at Thompson's construction for a use-case of $\varepsilon$-transitions. While you could adapt the construction to do without, it's much clearer and easier to prove correct in this way. $\endgroup$
    – Raphael ♦
    Jan 31, 2016 at 11:10
  • $\begingroup$ unrelated with your question, but would you mind to share what tool/software/website you used to draw automata this beautiful? $\endgroup$
    – kate
    Sep 23, 2020 at 9:11

1 Answer 1

Reset to default
3
$\begingroup$

Your first drawing is a DFA (and thus an NFA) and does match the language described. The NFA with $\varepsilon$ transitions is a fairly natural (and mechanical) translation of the regular expression, but other than that, it isn't inherently "more correct" than the NFA you started with.

The only confusion I see here other than uncertainty is once you validated that your NFA was a DFA you seemed to have just taken it for granted that it was minimal. Starting from your DFA, you could have noticed that S4 has the same out-transitions as S2 and that they might possibly be joined. Doing so would have immediately produced the final DFA.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you, I actually just realized that! OK, so one my main takeaways are to scrutinize the end product to see if any states can be combined, and one hint that states can be combined is the out-transitions of the states are the same. $\endgroup$
    – justAnotherGuy
    Jan 31, 2016 at 9:06

Your Answer

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

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