reverse automata mininum states

Question

There is a formal proof for the following sentence?

For every $k$ there is a DFA (deterministic finite automaton) $M$ with $k+2$ states such that every automaton that accepts the language $L(M)^R$ ($R$ = Reverse) has at least $2^k$ states

thanks.

Answer 1

I assume that you meant "... such that every deterministic automaton that accepts the language $L(M)^R$...", otherwise the statement isn't true.

It's known that there are some languages accepted by an $n+1$-state NFA for which the smallest equivalent DFA requires $2^n$ states. For example, Hopcroft/Motwani/Ullman show this in their Introduction to Automata Theory, Languages, and Computation (p. 65 in my edition). One such language is the set of all strings over $\{0, 1\}$ for which the $n$-th character from the end is $1$.

Now consider the language consisting of those strings for which the $k$-th symbol from the start is $1$. It's easy to construct an $k+2$-state DFA $M$ for this language. However, the language $L(M)^R$ is just the one we noted above, requiring at least $2^k$ states.