2
$\begingroup$

Just as the question asks, I am trying to understand the relationship between the number of accept states a DFA has (not necessarily the total number of states) and the languages it can accept.

I understand that the pumping lemma can be used to show that if a language has a length greater than the number of states, which is the pumping length, then it may not be a regular language. However, I don't understand how a language can be rejected by a DFA based on the number of accept states it has.

For example, I know that a* \cup b* is not a regular language because of the pumping lemma, but how do I know that it is not accepted by a DFA with only 1 accept state?

$\endgroup$
  • 1
    $\begingroup$ A few things: all regular languages are accepted by DFAs; anything accepted by a DFA is a regular language; $a^* \cup b^*$ is a regular language; this language is accepted by a DFA with one accepting state. More generally: the Myhill-Nerode theorem talks about the minimum number of states which a DFA must have in order to recognize a language. It has to do with how many equivalence classes the language has with respect to the indistinguishability relation. Is your question "how does the number of accepting states in minimal DFAs characterize the regular languages they accept?" $\endgroup$ – Patrick87 Oct 7 '14 at 22:40
  • $\begingroup$ Corrected the title to reflect my question a bit better. $\endgroup$ – Zahra Oct 7 '14 at 23:09
  • $\begingroup$ Thanks, the title is better now. But now the body of the question seems to be asking for something different from the title. The title seems to be asking for an example of a regular language with a certain property, whereas the body seems to be asking for a characterization of the minimal number of accepting states needed for a language, in terms of some property of the language. Which do you want? Please make sure that the body of the question contains the question you want answered. And, please edit the question to address the comments and misconceptions that Patrick87 provided. $\endgroup$ – D.W. Oct 7 '14 at 23:16
8
$\begingroup$

$\{\lambda, a, a^2, \dots, a^n\}$. All states in which these words are accepted must be different, in order to avoid loops (and stay finite).

$\endgroup$
5
$\begingroup$

Yes, there is a simple generalization of the Myhill-Nerode theorem that provides the characterization you seem to be looking for.

Let $\sim$ be the equivalence relation defined by the Myhill-Nerode theorem, i.e., $x \sim y$ if there is no suffix $z$ such that exactly one of $xz,yz$ are in $L$. Let $S$ denote the set of equivalence classes of $\sim$, i.e., $S = \{[x] : x \in \Sigma^*\}$, where $[x] = \{y \in \Sigma^* : x \sim y\}$. The Myhill-Nerode theorem tells us that any DFA for $L$ must have at least $|S|$ states. We can think of $S$ as the statespace of the minimal DFA that accepts $L$.

Now define $A$ to be the set of equivalence classes that contain at least one element of $L$, i.e., $A= \{[x] : x \in L\}$. Note that $A \subseteq S$. Also, we can think of $A$ as the set of accepting states for the minimal DFA that accepts $L$. In particular, any DFA that accepts $L$ must have at least $|A|$ accept states: consider any DFA $M$ that accepts $L$; then there is a function mapping the statespace of $M$ to $S$, and mapping the set of accepting states to $A$. (See the proof of the Myhill-Nerode theorem for the construction of this function.)

Therefore, $|A|=|\{[x] : x \in L\}|$ provides a lower bound on the number of accepting states of any DFA that accepts $L$, in terms of a property of $L$. If you find a language $L$ where $|A|>n$, then you know that there is no DFA that has $\le n$ accepting states and that accepts $L$.

$\endgroup$

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.