16
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ If I understand correctly, the question is to decide, given a regular language $L$, whether $S(L)$ is context-free or not. $\endgroup$ – J.-E. Pin Oct 30 '16 at 8:55
  • 2
    $\begingroup$ 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. $\endgroup$ – D.W. Oct 30 '16 at 12:58
  • $\begingroup$ @D.W. 1. Either would be fine, but I would prefer sufficient conditions. 2. Thanks for the tip! $\endgroup$ – Ryan Oct 30 '16 at 15:48
  • 1
    $\begingroup$ @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! $\endgroup$ – aelguindy Oct 30 '16 at 17:30
  • $\begingroup$ 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. $\endgroup$ – chi Nov 9 '16 at 14:13
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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. $\endgroup$ – Ryan Nov 9 '16 at 19:54
  • $\begingroup$ @Ryan the number of "patterns" xuy where u labels a loop is finite, so we can guess which one we are reading. $\endgroup$ – Denis Nov 9 '16 at 19:59
  • $\begingroup$ I edited to clarified this part. $\endgroup$ – Denis Nov 10 '16 at 1:06
  • $\begingroup$ 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$. $\endgroup$ – holf Nov 10 '16 at 11:05
  • $\begingroup$ @holf yours does not seem to work for $a^*b^*$ $\endgroup$ – Denis Nov 10 '16 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.