Question

The construction in Theorem 1.54 shows that every GNFA is equivalent to a GNFA with only two states. We can show that an opposite phenomenon occurs for DFAs. Prove that for every $\mathit{k}\mathbf{>}\mathbf{1}$, a language $\mathit{x}\mathit{A}\mathit{k}\mathbf{\subseteq }\left\{0,1\right\}$exists that is recognized by a DFA with k states but not by one with only$\mathit{k}\mathbf{-}\mathbf{1}$ states

Short answer

It can be said that no DFA’s is equivalent to a DFA with lesser states.

Step-by-step solution

Introduction

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

To Prove That no DFA are equivalent to a DFA

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,\dots ,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.

To Consider Ak={0,1}*0k-10*

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,\dots ,{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.