I am trying to figure out if there exists a DFA $M$ with $k+2$ states (for every $k\in \mathbb{N}$ ) so that every automaton which accepts $L(M)^R$ has at least $2^k$ states.
I am trying to find an example of such a DFA, any help?

  • $\begingroup$ possible duplicate of How to prove that DFAs from NFAs can have exponential number of states? $\endgroup$
    – D.W.
    Dec 6, 2013 at 0:36
  • $\begingroup$ @D.W. related, but not a duplicate. This is state complexity for reversal for DFA, the other is state complexity for NFA to DFA. Just reusing the same example in a new context. $\endgroup$ Dec 6, 2013 at 1:03
  • $\begingroup$ @HendrikJan, Yup. But... if you look at the examples given there, you will notice that they already satisfy exactly the criteria that the question asks for (they already have the desired property that the reversal requires exponentially more states). No additional modifications are needed. $\endgroup$
    – D.W.
    Dec 6, 2013 at 1:04
  • $\begingroup$ @D.W. Same example, true. But that is a clever application of a known result. As an example: if you want to prove non-closure properties for CFL you better use an old example rather than having to invent new ones. You do not say: we have seen $a^nb^nc^n$ for intersection so you cannot use it for complement (risking duplication). $\endgroup$ Dec 6, 2013 at 1:10
  • 1
    $\begingroup$ However I dislike the fact that this same question is also present at our sister site math.stackexchange. $\endgroup$ Dec 6, 2013 at 9:09

1 Answer 1


This is related to the usual NFA to DFA complexity problem. Strings over $\{a,b\}$ such that the $k$-th letter is an $a$.

Precise bounds for a general alphabet $\Sigma$ are given by @AntonTrunov. Then again the minimal DFA for the language has $k+2$ states, whereas the reversal needs $\frac{|\Sigma|^k-1}{|\Sigma|-1}+1$ states, assuming $|\Sigma|>1$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.