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$
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$
  • 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$ – Luke Mathieson Sep 22 '15 at 6:45
  • $\begingroup$ Gotcha. I somehow attributed the "+1" to $\epsilon$ transitions, rather than to the state being rejecting. $\endgroup$ – David Richerby Sep 22 '15 at 7:21
  • $\begingroup$ @DavidRicherby, ahh, actually that's worth explaining in the answer, ta. $\endgroup$ – Luke Mathieson Sep 22 '15 at 8:53

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.