1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What are your thoughts on the question? Do you have any ideas? $\endgroup$ – Yuval Filmus May 29 '18 at 9:08
  • $\begingroup$ You also need $L$ to be "non-universal" (i.e., its complement needs to be non-empty). $\endgroup$ – Yuval Filmus May 29 '18 at 9:16
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.