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.