10
$\begingroup$

I came across this question in a test and I had to answer whether it is true or false.

DFA with single final state has the same powers as DFA with more than one final state.

I was confused by what definition of "power" have they used. Generally, we always use power as a term to represent the class of languages a machine accepts and to me, it seems that since it is a DFA, regardless of the number of accept states, the power should be the same.

However, the question says that this is false and a DFA with more than one final state is more powerful. Is that true? I've never come across this in any textbook.

$\endgroup$
3
  • 2
    $\begingroup$ The question is whether the power of the DFA is decreased by restricting the number of allowed final states to one. The answer is given here: cs.stackexchange.com/q/30718/4287 $\endgroup$ Commented Dec 6, 2018 at 11:53
  • $\begingroup$ @HendrikJan Is it possible for you to elaborate on your explanation in the example you've mentioned there? I am having a hard time understanding how that relates to my question. $\endgroup$
    – Gokul
    Commented Dec 6, 2018 at 13:29
  • $\begingroup$ I just posted an answer that used @HendrikJan's idea and example. $\endgroup$
    – John L.
    Commented Dec 7, 2018 at 4:07

2 Answers 2

9
$\begingroup$

I was confused by what definition of "power" have they used. Generally, we always use power as a term to represent the class of languages a machine accepts

There are, equivalent or nonequivalent, definitions of "power" and "has power" in computation theory. Here is one definition of power that is suitable for the current situation.

A (descriptive) power means a set of languages over an alphabet. Given a set of automata $S$, the (descriptive) power of $S$ is $P(S)=\{L(A)\mid A\in S\}$, where $L(A)$ is the language accepted by $A$. Given two sets of automata $S_1$ and $S_2$, if $P(S_1)=P(S_2)$, we say $S_1$ and $S_2$ has the same power or $S_1$ is as powerful as $S_2$ or $S_1$ is equivalent to $S_2$ in power. If $L(S_1)\subsetneq L_{S_2}$, we say $S_1$ is less powerful than $S_2$.

For a more rigorous definition, we should define the meaning of "$L$ is the language accepted by $A$". However, since that meaning is clear in the context of DFA and NFA, we will skip it here. Note that we only talk about "power" for a set of automata. When we compare powers, the same alphabet is usually implied.

Since it is a DFA, regardless of the number of accept states, the power should be the same.

Take a moment to reflect. Are you sure you have seen or proved that claim? I would bet you have not, although there are many popular cases of different automata having the same power, such as NFA and DFA have the same power.

On the other hand, there are many cases where if you restrict some aspect of automata, you will decrease its power, which is of course reasonable. For example, if you restrict the stacks of PDAs to be finite, they become equivalent in power to finite automata. If you restrict (deterministic) PDAs to only have one or two states, you will get various powers depending on how PDAs are defined to accept (here are some result). If you restrict Turing machines to be read-only, they can be considered as two-way finite automata, which have the same power of the usual DFAs.

For an extreme example, if you change DFAs to DFAs with only one state, you will only have two DFAs, one DFA whose start state is not an accept state and one DFA whose start state is also an accept state, whose power is two languages, the empty language and the language of all words over the alphabet.

DFA with single final state has the same power as DFA with more than one final state.

Final states are also commonly called accept states in the context of DFA or NFA. Fix our alphabet. Let $S_n$ be the set of all DFA that have $n$ accept states, where $n\ge1$. We will show a more general proposition.

(Less accept states, less power). $S_n$ is less powerful than $S_{n+1}$ for all $n$.

Proof. Suppose we have $A\in S_n$. Let $A'\in S_{n+1}$ be the same as $A$ except that $A'$ has one extra accept state that is not used by any transition. Since $L(A)=L(A')$, $S_n$ is at most as powerful as $S_{n+1}$.

Let $a$ be a symbol in the alphabet. Here is the beautiful example by Hendrik Jan. Let $K=\{\lambda, a, a^2, \dots, a^n\}$.

Suppose $K=L(B)$ for some DFA $B$. For the sake of contradiction, suppose both $a^i$ and $a^j$, where $i<j$, are accepted by state $q$ in $B$. That means, given $j-i$ $a$'s, $q$ is transitioned to itself. So given another $j-i$ $a$'s, $q$ will be transitioned to itself again. And so on. That means, all strings $a^i, a^j, a^{i+2(j-i)}, a^{i+3(j-i)}, \cdots$ are accepted. That contradicts the fact that $B$ only accepts the $n+1$ strings in $K$. So all states of $B$ in which these words are accepted must be different. That is, $B$ must have at least $n+1$ accept states.

I will leave it as an exercise for you to construct a DFA with $n+1$ accept states that accepts $K$. Since $K\not\in P(S_n)$ but $K\in P(S_{n+1})$, we have proved "less accept states, less power".


Exercise 1. Show that DFAs with $n$ reject states have less power than DFAs with $n+1$ reject states for all $n\ge1$.

Exercise 2. Let $S_{m,n}$ be the set of DFAs with $m$ accept states and $n$ reject states, $m+n\ge1$. Compare their powers.

Exercise 3. (Provided by Mr. Sigma) Show that NFAs with a single accept state have the same power as all NFAs.

Exercise 4. Show that NFAs with a single accept state and without $\epsilon$-transition have the same power as all NFAs.

$\endgroup$
4
  • 1
    $\begingroup$ +1. It's helpful but I tend to disagree on your exercise. Every NFA with $n$ accept states can be converted to single accept state by converting final to non final states and putting an $\epsilon$ edge from ex-final states to newly created final state. Am I somewhere wrong? $\endgroup$
    – Mr. Sigma.
    Commented Dec 7, 2018 at 15:54
  • 1
    $\begingroup$ How can it happen? There is only one way transition from ex-final to new final. $\endgroup$
    – Mr. Sigma.
    Commented Dec 7, 2018 at 16:13
  • 1
    $\begingroup$ @Mr.Sigma.'s construction is correct. In more detail, add a new accepting state to the NFA, and give it no outgoing transitions. Make every old accepting state non-accepting and add an $\epsilon$-transition from each of them to the new accept state. It's easy to see that the new machine accepts an input iff the old machine has a computation path that ends in an accepting state, i.e., iff the old machine accepts. The key point is that the new accepting state is a dead state so, if you jump to it before the end of the word, the run will reject. $\endgroup$ Commented Dec 7, 2018 at 16:14
  • 1
    $\begingroup$ @Mr.Sigma. Super good catch. David, nice explanation. Now I recall I did see that NFA with one state has the same power. I am changing your comments to a new exercise. $\endgroup$
    – John L.
    Commented Dec 7, 2018 at 16:24
8
$\begingroup$

Consider the regular language $a^*\vert b^*$. The accepting states for $a^*$ and $b^*$ must be different, because from the accepting state for $a^*$ there's no transition with a $b$ to an accepting state, but from the accepting state for $b^*$ there is one.

$\endgroup$
3
  • 1
    $\begingroup$ Can this one example really prove languages accepted by DFA with single final state are less in number than the languages accepted by DFA with many final states? $\endgroup$
    – Mr. Sigma.
    Commented Dec 6, 2018 at 14:14
  • 1
    $\begingroup$ You can always just add an unreachable final state. Thus, every DFA with a single final state can be translated into a DFA with many final states. This, together with the answer is a proof, I think. $\endgroup$ Commented Dec 6, 2018 at 15:23
  • 1
    $\begingroup$ Nice answer. If I may be nitpicky, it misses the case when the alphabet has only one symbol. $\endgroup$
    – John L.
    Commented Dec 7, 2018 at 4:03

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.