Charakterystyka dla której nie jest CFL?

Jest to standardowy dowód w kursach z automatami, że dla i że nie jest językiem bezkontekstowym.$L = \Sigma^\star$$|\Sigma| \ge 2$$S(L) = \{ww : w \in L\}$

Prawdą jest również, że dla każdego skończonego , jest skończone (a zatem CFL). Zgaduję, że jest nieskończony i regularny nie jest „wystarczający”, aby nie był CFL. Edycja : a co z bez CFL ?$L$$S(L)$$L$$S(L)$$L$

Czy istnieje jakaś charakterystyka tego, że ma S ( L ) nie będący CFL?$L$$S(L)$

Bardziej rozbudowany komentarz z przypuszczeniem, ale tutaj jest warunek, który wydaje się wychwytywać problem, w kontekście zwykłego dla S ( L ) bez kontekstu.$L$$S(L)$

Warunek W minimalnym DFA dla L każda ścieżka akceptacji zawiera najwyżej jedną pętlę.$A$$L$

Wyjątek: dozwolone są dwie pętle, jeśli ich etykiety i etykieta prefiksu przed pierwszą pętlą wszystkie dojeżdżają do pracy, a sufiks po drugiej pętli jest pusty. Na przykład jest w porządku.$aa^*b(aa)^*$

Przypomnij sobie, że dwa słowa i v dojeżdżają, jeśli są mocami tego samego słowa t . Możemy założyć, że sufiks jest pusty, ponieważ nie może być niepusty i dojeżdżać do pracy z etykietą drugiej pętli w DFA.$u$$v$$t$

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 (dla wystąpień ), czytaj x y , pop n razy, push m razy (dla v ), czytaj x y , pop m razy.$u$$xy$$n$$m$$v$$xy$$m$

Końcowy PDA to połączenie PDA dla każdego wzorca.

Konieczne (ręczne falowanie) Jeśli istnieje ścieżka z dwiema pętlami, nawet w najprostszym przypadku, w którym musisz wziąć jedną, a następnie drugą (na przykład ), musisz pamiętać, ile razy każda z nich została wzięta, ale struktura stosu zapobiega powtarzaniu ich w tej samej kolejności. Zauważ, że fakt, że DFA jest minimalny, jest ważny w charakterystyce, aby uniknąć użycia dwóch pętli, gdy jedna może wystarczyć.$a^*b^*$

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.