# What is the state complexity of the copy language?

Let a number $n$ be given. Consider the following language $L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \}$.

In words, $L_n$ is the set of copy strings of length $2n$.

Consider the following state complexity function $s$ such that $s(n)$ is the number of states in the smallest Pushdown Automata that recognizes $L_n$.

Question: Can you formally prove any meaningful lower bound for $s(n)$?

My Conjecture: $s(n) = 2^{\Theta(n)}$.

Known Upperbound: $s(n) \leq \mathrm{poly}(n) \cdot 2^{\frac{n}{2}}$.

Rules:

(1) The stack alphabet must be binary.

(2) The input tape is one-way and can't stop on any input character.

• I currently don't have any meaningful lower bound. It seems to me you might be able to prove a lower bound for the number of variables you need for a CFG that recognize the language. Although, I'm not even totally sure of this. Commented Jul 23, 2015 at 4:36
• My intuition is that as you push characters from the input tape to the stack, you run into a problem. If you ever want to retrieve these bits later on, you have to throw away all the bits that you pushed above it. In other words, it appears that the stack doesn't help you because the more you push to it, the more you're forced to forget later on. Commented Jul 23, 2015 at 4:39
• Remark: For DFA's (automata without a stack), you can prove an exponential state complexity lower bound. Commented Jul 23, 2015 at 4:45
• Can you show a reasonable lower bound for the simpler problem of $\{0^k1^l0^k1^l\}$? Commented Jul 23, 2015 at 7:53
• A more precise upper bound seems to be $(n+3)2^{n/2}$ states. Commented Jul 25, 2015 at 12:29

The technique described by Yuval:

Do there exists polynomial size CFG that describe this finite language?

( you may also read: Lower bounds on the size of CFGs for specific finite languages )

allows to show very easily an exponential lower bound for CFGs. Let $G$ a grammar in Chomsky Normal Form for $L_n$. For every word $w\in \{0,1\}^n$ there exists at least one non-terminal $A(w)$ accepting a subword $s(w)$ of $ww$ having length between $n/2$ and $n$. Let $p(w)$ be a position in $ww$ where this subword occurs. There are at least $n/2$ bits common to all words $w,w'$ such that $A(w)=A(w')$ and $p(w)=p(w')$. Consequently, there can be at most $2^{n/2}$ words that have the same $A(w)$ and $p(w)$. Hence there are at least $2^{\Theta(n)}$ non-terminals.

Furthermore, the PDA can be converted into a CFG in CNF, of polynomial size so this also gives the $2^{\Theta(n)}$ bound on the state complexity of $L_n$.

• Awesome, thanks again! I see now and will think about it to confirm. :) Commented Jul 24, 2015 at 15:38
• Right again: changing length from $[n,2n]$ to $[n/2,n]$ introduced another issue. I had to refine the argument in a way similar to Yuval's (counting overlaps). Now I believe it is correct, at last. I edited the answer and deleted my comments Commented Jul 28, 2015 at 8:46
• In case it helps anyone else: note that once $(A(w),p(w))$ has been chosen, $A(w)$ can only ever yield the single subword of $ww$ that begins at position $p(w)$. So this actually shows that any correct CNF-CFG for this language must have many nonterminals that each generate a single long subword. Commented Aug 4, 2015 at 10:07
• See also Theorem 7 in my paper: cs.toronto.edu/~yuvalf/CFG-LB.pdf. Commented Nov 15, 2015 at 23:21
• @YuvalFilmus It's worth also noting that Andras spent a bit of time trying to get the upper and lower bounds to match. My friend Pepe and I defined a general class of finite languages and applied the technique to them. We never wrote anything up though. If you ever have any related problems, we would be more than willing to collaborate. Thanks again. Commented Nov 16, 2015 at 3:13