automata theorem: existance of a DFA

Question

I need to prove that for every k, there's a DFA M with k+2 states, so in every automat M' who accepts the language reverse(L(M)) there are at least 2^k states.

Help would be really appreciated.

Thanks :)

Answer 1

Assuming that the alphabet set contains at least two elements, let it be {0,1}.

Next, let M be the automata accepting the language L defined as:

All the strings which k-th position is 1

defined as:

M = {Q,{0,1},q₀,{q_k+1},δ}, where

Q={q₀,q₁,...,q_k,q_F}

δ(q_i,a) = q_i+1, for a in {0,1} and i=0,1,...,k-2

δ(q_k-1,0) = q_F,

δ(q_k-1,1) = q_k,

δ(q_F,a) = q_F, for a in {0,1}

Note that M has exactly k+2 states, and that it accepts the language L.

Now, note that the language reverse(L(M)) can be translated as:

All the strings which k-th position from the end is 1

To recognize that language, note that we need to remember the last k symbols, because we don't know when the string will end. We know that there are at least 2^k possible strings of length k (since the alphabet size is at least 2).

So using a DFA, we need at least 2^k states, each to represent one possible string of length k. _▢

Author's note:

The idea of this proof is to find a language which is "easy" to be recognized in normal way, but "difficult" when is read backward. Through experience, I remember that fixing the k-th position from the beginning is "easy", while k-th position from the end is "difficult", hence my answer.