Search code examples
regular-language

Determine how many states the minimal DFA will have

This is the pumping lemma to demonstare that a language is not regular:If L is a regular language,there is a const N such that, for each z in L, with |z|>=N, is possibile to divide z in three sub-strings (uvw=z)such that:

1)|uv|<=N;  
2)|v|>=1;  
3)For each k>=0, uv^kw in L.

N must be less or equal than the minumum number of states of the DFA accepting L.So to apply the pumping lemma I need to know how many states will have the minimal DFA accepting L.Is there a way to know how many states will have backwards?So is possibile to know the minimal number of states without building the minimal DFA?

Solution

  • N must be less or equal than the minumum number of states of the DFA accepting L

    N cannot be less than the number of states in a minimal DFA accepting L; otherwise, the DFA couldn't accept L (if it could, you would have a DFA accepting L smaller than the minimal DFA accepting L, a contradiction). We can safely assume that N is equal to the number of states in the minimal DFA accepting L (such DFAs are unique).

    So to apply the pumping lemma I need to know how many states will have the minimal DFA accepting L

    This is not strictly true. In most pumping lemma proofs, it doesn't matter what N actually is; you just have to make sure that the target string satisfies the other properties. It is possible, given a DFA, to determine how many states a minimal DFA will have; however, if you have a DFA, there's no need to bother with the pumping lemma, since you already know L is regular. In fact, determining an N such that there's a minimal DFA with N states accepting L constitutes a valid proof that the language in question is indeed regular.

    So is possibile to know the minimal number of states without building the minimal DFA?

    By analyzing the description of the language and using the Myhill-Nerode theorem, it is possible to construct a proof that a language is regular and find the number of states in a minimal DFA, without actually building the minimal DFA (although once you have completed such a proof using Myhill-Nerode, construction of a minimal DFA is a trivial exercise). You can also use Myhill-Nerode as an alternative to the pumping lemma to prove languages aren't regular, by showing a minimal DFA for the language would need to have infinitely many states, a contradiction.

    Please let me know whether these observations answer your questions; I will be happy to provide additional clarification.