91Ó°ÊÓ

The GNFA Convert G is equivalent to G. By Induction on k, the number of states of G.

It is being given that if there are two states GNFA then is correspondingly equal to the GNFA. But here user need to prove that in DFA subsequently opposite phenomenon occurs.

It implies user need to prove that no DFA are equivalent to a DFA with lesser states.

Assume $A_k$ be the set of words of length at least $k-1$. Therefore, it can be said that role="math" localid="1663228503830" $A_k$has at least equivalence classes of words length$0,1,2,…,k-2andk-1$ or more. So, it is clear from this that $A_k$requires a DFA with states $k$.

For any DFA fewer than states $k$, by Pigeon Hole Principle, two of the$k$ strings cause the machine to loop in same state results in a rejection from the DFA.

Consider $A_k=\{0,1\}*0^{k-1}0*$for $k>1$.

Now a DFA with exactly k states can recognize the language $A_k$. Starting from the start state there is a state in the DFA for each 0 it had read after the last 1.

After $k-1  0\text{'}s$it arrives at an accepting state whose further transitions are self-loops. Now based on the language let say $A_k$be the set consisting of the strings $10,100,…,{10}^{k-1}$. If the DFA consist of fewer than$k$ states, then by the Pigeonhole Principle two these strings cause a loop to a single state. Hence the machine fails to accept the strings.

Hence, it can be said that no DFA’s is equivalent to a DFA with lesser number of states.