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 '13 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$ – Hendrik Jan Dec 6 '13 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 '13 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$ – Hendrik Jan Dec 6 '13 at 1:10
  • 1
    $\begingroup$ However I dislike the fact that this same question is also present at our sister site math.stackexchange. $\endgroup$ – Hendrik Jan Dec 6 '13 at 9:09

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$.

| cite | improve this answer | |

Your Answer

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