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$
$\endgroup$
6
-
$\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$– Hendrik JanDec 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$– Hendrik JanDec 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$– Hendrik JanDec 6, 2013 at 9:09
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
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$.
answered Dec 5, 2013 at 19:06