<p>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.</p>

<p><strong>Condition</strong>
In the minimal DFA $A$ for $L$, any accepting path contains at most one loop.</p>

<p><em>Exception:</em> 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.</p>

<p>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.</p>

<p><strong>Sufficient</strong>
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$. </p>

<p>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.</p>

<p>The final PDA is the union of the PDAs for each pattern.</p>

<p><strong>Necessary</strong>
(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.</p>

<p>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.</p>

CC BY-SA 3.0
2016-11-09T19:54:12.763Z
"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
CC BY-SA 3.0
2016-11-09T19:59:29.913Z
@Ryan the number of "patterns" xuy where u labels a loop is finite, so we can guess which one we are reading.
Denis
CC BY-SA 3.0
2016-11-10T01:06:36.427Z
I edited to clarified this part.
Denis
CC BY-SA 3.0
2016-11-10T11:05:00.227Z
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
CC BY-SA 3.0
2016-11-10T13:03:30.773Z
@holf yours does not seem to work for $a^*b^*$
Denis
CC BY-SA 3.0
2016-11-10T14:10:35.487Z
@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
CC BY-SA 3.0
2016-11-10T14:16:30.147Z
@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
CC BY-SA 3.0
2016-11-10T14:28:43.720Z
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
CC BY-SA 3.0
2016-11-10T14:37:14.797Z
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
CC BY-SA 3.0
2016-11-10T14:40:59.073Z
Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/48273/discussion-between-denis-and-holf).
Denis
CC BY-SA 3.0
2016-11-09T16:08:26.367Z
2016-11-10T10:47:02.737Z
2016-11-10T10:47:02.737Z
Denis
<p>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.</p>

<p>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. <em>Edit</em>: what about non-CFL $L$?</p>

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

CC BY-SA 3.0
2016-10-30T08:55:12.443Z
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
CC BY-SA 3.0
2016-10-30T12:58:41.327Z
1. Can you tell us more about what kind of characterization you're looking for?  Are you looking for an algorithm that, given $L$, decides whether $S(L)$ is context-free?  Are you looking for some  conditions on $L$ that suffice to ensure $S(L)$ will be context-free?  What form would you like a characterization to take?  2. If you don't get any answers after a few days and would prefer to see this on CSTheory.SE, feel free to flag it for moderator attention and ask to have it migrated.
D.W.
CC BY-SA 3.0
2016-10-30T15:48:23.827Z
@D.W. 1. Either would be fine, but I would prefer sufficient conditions. 2. Thanks for the tip!
Ryan Dougherty
CC BY-SA 3.0
2016-10-30T17:30:56.030Z
@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
CC BY-SA 3.0
2016-11-09T14:13:48.433Z
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
CC BY-SA 3.0
2016-11-09T22:37:44.533Z
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
CC BY-SA 3.0
2016-11-10T14:35:05.790Z
another conjecture : if $L$ is not regular then $S(L)$ is not a CFL.
Denis
CC BY-SA 3.0
2016-11-10T16:16:15.640Z
@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
CC BY-SA 3.0
2016-11-13T04:10:13.767Z
@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
<context-free>
Characterization of $L$ for which $\{ww : w \in L\}$ is not a CFL?
Ryan Dougherty
# Characterization of $L$ for which $\{ww : w \in L\}$ is not a CFL?

(Asked by: username_0 on 2016-10-29)

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?

**Tags:** context-free
> **Comments:**
> **username_1**: If I understand correctly, the question is to decide, given a regular language $L$, whether $S(L)$ is context-free or not.  
> **username_2**: 1. Can you tell us more about what kind of characterization you're looking for?  Are you looking for an algorithm that, given $L$, decides whether $S(L)$ is context-free?  Are you looking for some  conditions on $L$ that suffice to ensure $S(L)$ will be context-free?  What form would you like a characterization to take?  2. If you don't get any answers after a few days and would prefer to see this on CSTheory.SE, feel free to flag it for moderator attention and ask to have it migrated.  
> **username_0**: @D.W. 1. Either would be fine, but I would prefer sufficient conditions. 2. Thanks for the tip!  
> **username_3**: @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!  
> **username_4**: 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.  
> **username_5**: 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 :-).  
> **username_6**: another conjecture : if $L$ is not regular then $S(L)$ is not a CFL.  
> **username_0**: @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...)  
> **username_6**: @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$.  

---

## 1 answers

### Answer by username_6 on 2016-11-09. Score: 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.

> **Comments:**
> **username_0**: "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.  
> **username_6**: @Ryan the number of "patterns" xuy where u labels a loop is finite, so we can guess which one we are reading.  
> **username_6**: I edited to clarified this part.  
> **username_7**: 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$.  
> **username_6**: @holf yours does not seem to work for $a^*b^*$  
> **username_7**: @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.  
> **username_6**: @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$.  
> **username_6**: 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.  
> **username_7**: 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.  
> **username_6**: Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/48273/discussion-between-denis-and-holf).  

---

