patternMinor
Show that for any natural number n, there is a regular language that is not recognized by any DFA with at most n final states
Viewed 0 times
showdfanumberwithanyregularstateslanguagerecognizedthat
Problem
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
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?Solution
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$.
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$.
Context
StackExchange Computer Science Q#30718, answer score: 5
Revisions (0)
No revisions yet.