Characterization of $L$ for which $\{ww : w \in L\}$ is not a CFL?

Question

It is a standard proof in automata courses that for $L = \Sigma^\star$ and $|\Sigma| \ge 2$ that $S(L) = \{ww : w \in L\}$ is not a context-free language.

It is also true that for any finite $L$, $S(L)$ is finite (and therefore a CFL). I'm guessing that $L$ being infinite and regular are not "sufficient" for $S(L)$ being not a CFL. Edit: what about non-CFL $L$?

Is there any characterization of what $L$ have $S(L)$ not being a CFL?

If I understand correctly, the question is to decide, given a regular language $L$, whether $S(L)$ is context-free or not. — J.-E. Pin, Oct 30 '16 at 08:55
@D.W. 1. Either would be fine, but I would prefer sufficient conditions. 2. Thanks for the tip! — Ryan Dougherty, Oct 30 '16 at 15:48
@Ryan just sufficient conditions? Well, here are a couple: (a) L is regular and for every $w$ in $L$, $w = w^R$ (b) L is CF and for all $n$, $L \cap \Sigma^{n}$ is either empty or equal to $\Sigma^{n}$. These are definitely not necessary though. If you do not get answers here, please do move the question to cstheory. I am really curious about necessary and sufficient conditions! — aelguindy, Oct 30 '16 at 17:30
Infinite and regular $L$ is indeed not sufficient for $S(L)$ not CF. If $\Sigma = {a,b,c},L = a^$ then $S(L) = (aa)^$ which is regular, hence CF. — chi, Nov 09 '16 at 14:13
Another idea (conjecture) is the following: assuming $\Sigma = {0,1}$, it's enough that the Parick image of the (regular) $L$ contains at least one linear set of the form ${(|w|_0,|w|_1)}={(a_1+b_1 n,a_2+b_2 n),n\in \mathbb{N}}$ and both $b_1,b_2 \neq 0$ where $|w|_0$ (resp. $|w|_1$) is the number of $0$s (resp. $1$s) of $w$. (for larger $\Sigma$ the condition becomes $\exists i \neq j, b_i, b_j \neq 0$)... I'll try to formalize/prove (or fix/delete) it in the next days (monday :-). — Marzio De Biasi, Nov 09 '16 at 22:37
another conjecture : if $L$ is not regular then $S(L)$ is not a CFL. — Denis, Nov 10 '16 at 14:35
@Denis I figured that too -- do you have a conjecture as to when the "transition" to being NCFL happens? (Starts off regular/finite with finite $L$, and some infinite $L$ surely have $S(L)$ a CFL, but there has to be a "transition" somewhere...) — Ryan Dougherty, Nov 10 '16 at 16:16
@Ryan: yes, see my answer, the full conjecture would be: $S(L)$ is not CFL if $L$ is not regular of if there are $x,u,y,v,z$ such that $u,v$ non empty, $x,u,v,z$ are not power of a same word, and $xu^yv^z\subseteq L$. — Denis, Nov 13 '16 at 04:10

Denis · Answer 1 · 2016-11-10T10:47:02.737

2

More of an extended comment with a conjecture, but here is a condition that seems to capture the problem, in the context of regular $L$ for $S(L)$ to be context-free.

Condition In the minimal DFA $A$ for $L$, any accepting path contains at most one loop.

Exception: two loops are allowed if their labels and the label of the prefix before the first loop all commute, and the suffix after the second loop is empty. For instance $aa^*b(aa)^*$ is ok.

Recall that two words $u$ and $v$ commute if they are powers of a same word $t$. We can assume the suffix empty, because it cannot be non-empty and commute with the label of the second loop in a DFA.

Sufficient Assume the condition, you build a PDA for $L$ by treating each accepting pattern $xuy$ of $A$ where $u$ labels a simple loop. We want to accept words of the form $xu^nyxu^ny$. We read $x$, push a symbol for every occurence of $u$, read $yx$, then pop a symbol for every occurence of $u$, and finally read $y$.

About the exception, if we are in this case, a basic accepting path is of the form $xuyv$ where $u,v$ are the labels of the loops. We accept words of the form $xu^n y v^m xu^n y v^m$, but by assumption ($x,u,v$ commute) it is the same as $u^nxyu^n v^mxyv^m$, which can be done by a PDA: push $n$ times (for occurences of $u$), read $xy$, pop $n$ times, push $m$ times (for $v$), read $xy$, pop $m$ times.

The final PDA is the union of the PDAs for each pattern.

Necessary (handwaving) If there is a path with two loops, even in the simplest case where you must take one then the other (for instance $a^*b^*$), you must remember how many times each one is taken, but the stack structure prevents you to repeat them in the same order. Notice that the fact that the DFA is minimal is important in the characterization, to avoid using two loops when one could suffice.

For now the necessary part is only a conjecture, and more exceptions could be needed to get the exact condition, I would be interested in counter-examples.

edited Nov 10 '16 at 10:47

answered Nov 09 '16 at 16:08

Denis

8,843
28
55

"and then reading w again, popping a symbol for every loop taken in the second occurence of the word" - but there are infinitely many such $w$! Unless I'm reading your argument incorrectly. – Ryan Dougherty Nov 09 '16 at 19:54
@Ryan the number of "patterns" xuy where u labels a loop is finite, so we can guess which one we are reading. – Denis Nov 09 '16 at 19:59
I edited to clarified this part. – Denis Nov 10 '16 at 01:06
The condition looks similar to me to another one I had in mind: S(L) is context free iff there do not exist words $u,v,w_1,w_2$, such that $w_1$ and $w_2$ are not prefix of each others and $u(w_1+w_2)^*v \subseteq L$. – holf Nov 10 '16 at 11:05
@holf yours does not seem to work for $a^b^$ – Denis Nov 10 '16 at 13:03
@Denis yes thank you I realized it too late as well. I may have another condition that seems closer to yours but machine-independant and then without side conditions. – holf Nov 10 '16 at 14:10
@holf I agree it can be reformulated in a machine-independent way, something like : S(L) is not CFL iff there exists words $x,u,y,v,z$ with $u,v$ non-empty and $x,u,v,z$ do not all commute, such that $xu^yv^z\subseteq L$. – Denis Nov 10 '16 at 14:16
the regularity assumption is still important though, because if L is not regular there is no reason why S(L) would be a CFL. For instance $L={a^pb: p\text{ prime}}$ satisfies the condition, but S(L) is not CFL. – Denis Nov 10 '16 at 14:28
I am trying a condition like $L$ is a finite union of language of the form $L_1.K(w).L_2$ with $L_1,L_2$ finite and $K$ is a regular language on unary alphabet ${a}$ and $K(w) = {w^n \mid a^n \in K}$. $S(L)$ is context free in this case. I can't find counter-example for the reverse statement. – holf Nov 10 '16 at 14:37
Let us continue this discussion in chat. – Denis Nov 10 '16 at 14:40

Characterization of $L$ for which $\{ww : w \in L\}$ is not a CFL?

1 Answers1