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$
2
  • $\begingroup$ What are your thoughts on the question? Do you have any ideas? $\endgroup$ May 29, 2018 at 9:08
  • $\begingroup$ You also need $L$ to be "non-universal" (i.e., its complement needs to be non-empty). $\endgroup$ May 29, 2018 at 9:16

1 Answer 1

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 and acknowledge you have read our privacy policy.

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