2
$\begingroup$

If I have a DFA with only one state that is not an accept state, it accepts only the empty set.

I get confused when if the DFA of one state is an accept state. Does this mean it accepts everything? Or could you have it only accept "a" and not "b". I guess I don't understand if not having an arrow out implies there is a second "invisible state"

In other words, for a DFA of one state, are there 2 or 4 distinct machines?

Thanks!

$\endgroup$

1 Answer 1

5
$\begingroup$

First let $\Sigma = \{a,b\}$.

Assuming that you're taking a strict approach, there has to be a transition from every state for every symbol in the alphabet, then you have only two possible DFAs (that accept $\emptyset$ and $\Sigma^{\ast}$ respectively).

If you allow a partial transition function, where missing transitions imply rejection (note that this can still be interpreted deterministically), then there are five different languages that can be accepted (strictly there's seven automata): $\emptyset$, $\{\varepsilon\}$, $a^{\ast}$, $b^{\ast}$ and $\Sigma^{\ast}$.

With a larger alphabet, in the partial function case, you get more of course. With $|\Sigma| = n$ there are $2^{n} + 1$ possible languages, from $2^{n+1}$ different automata (half produce the same language). You get $2^{n}$ from each possible choice of which symbols will have a transition in the case where the state is accepting, and the $+ 1$ from the case where the state is non-accepting (it doesn't matter what transitions you have then, the languages are all $\emptyset$).

$\endgroup$
3
  • 1
    $\begingroup$ @DavidRicherby, no epsilon transitions, just a partial function for the transition function instead of a [total] function. I don't particularly like this version, but some people do. You just get implicit early rejection. $\endgroup$ Sep 22, 2015 at 6:45
  • $\begingroup$ Gotcha. I somehow attributed the "+1" to $\epsilon$ transitions, rather than to the state being rejecting. $\endgroup$ Sep 22, 2015 at 7:21
  • $\begingroup$ @DavidRicherby, ahh, actually that's worth explaining in the answer, ta. $\endgroup$ Sep 22, 2015 at 8:53

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.