Let's assume that DFA $A$ over the alphabet $\Sigma$ and with states $Q$ is maximal if for every function $f\colon Q\rightarrow Q$ there exists such word $w \in \Sigma^{*}$, that $q \cdot w = f(q)$ for every state $q \in Q$. Let $L \subseteq \{a, b, c\}^{*}$ be a non-empty language recognized by a maximal automaton with $n$ states.
Prove that all DFAs recognizing language $L^R$ have got at least $2^n$ states.
Maximality implies that every state is reachable. Let $w_q$ by a word such that $q_0 \cdot w_q = q$.
Since $L$ is non-empty and its complement is also non-empty, there must be some accepting state $q_1$ and some non-accepting state $q_2$. For every subset $A \subseteq Q$, let $w_A$ be a word such that $q \cdot w_A = q_1$ for $q \in A$ and $q \cdot w_A = q_2$ for $q \notin A$.
I claim that if $A \neq B$ then $w_A^R$ and $w_B^R$ are not equivalent modulo $L^R$. Indeed, suppose (without loss of generality) that $q \in A \setminus B$. Then $w_A^R w_q^R \in L^R$ since $q_0 \cdot w_q w_A = q \cdot w_A = q_1$, whereas $w_B^R w_q^R \notin L^R$ since $q_0 \cdot w_q w_B = q \cdot w_B = q_2$. The result immediately follows.
