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 nie będący CFL? $L$ $S(L)$

context-free

— Ryan
źródło

Jeśli dobrze rozumiem, należy zadecydować, biorąc pod uwagę zwykły język

, czy

jest pozbawiony kontekstu, czy nie.

L

$L$

S (L)

$S(L)$

— J.-E.

1. Czy możesz nam powiedzieć więcej o tym, jakiej charakterystyki szukasz? Czy szukasz algorytmu, który, biorąc pod uwagę

, decyduje, czy

jest pozbawiony kontekstu? Czy szukasz warunków na

które wystarczą, aby

był pozbawiony kontekstu? Jaką formę chciałbyś przyjąć charakterystykę? 2. Jeśli po kilku dniach nie otrzymasz odpowiedzi i wolisz zobaczyć to na CSTheory.SE, możesz oflagować ją dla uwagi moderatora i poprosić o migrację.

L

$L$

S (L)

$S(L)$

L

$L$

S (L)

$S(L)$

— DW

@DW 1. Oba byłyby w porządku, ale wolałbym odpowiednie warunki. 2. Dzięki za wskazówkę!

— Ryan

@ Ryan tylko wystarczające warunki? Oto kilka: (a) L jest regularne i dla każdego

(b) L jest CF i dla wszystkich

jest albo puste, albo równe

. Nie są to jednak zdecydowanie konieczne. Jeśli nie znajdziesz tutaj odpowiedzi, przenieś pytanie do cstheory. Jestem naprawdę ciekawa niezbędnych i wystarczających warunków!

w

$w$

L

$L$

w = w^{R}

$w = w^R$

n

$n$

L \cap Σ^{n}

$L \cap \Sigma^{n}$

Σ^{n}

$\Sigma^{n}$

— aelguindy

Nieskończony i regularny

rzeczywiście nie wystarcza, aby

nie CF. Jeśli

wówczas

, który jest regularny, a więc CF.

L

$L$

S (L)

$S(L)$

Σ = {a, b, c}, L = a^{*}

$\Sigma = \{a,b,c\},L = a^*$

S (L) = (a a)^{*}

$S(L) = (aa)^*$

— chi

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

Warunek W minimalnym DFA dla 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 dojeżdżają, jeśli są mocami tego samego słowa . 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 , pop razy, push razy (dla ), czytaj , pop 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.

— Denis
źródło

"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

$w$ ! Unless I'm reading your argument incorrectly.

— Ryan

@Ryan the number of "patterns" xuy where u labels a loop is finite, so we can guess which one we are reading.

— Denis

I edited to clarified this part.

— Denis

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}

$u,v,w_1,w_2$ , such that

w_{1}

$w_1$ and

w_{2}

$w_2$ are not prefix of each others and

u (w_{1} + w_{2})^{*} v \subseteq L

$u(w_1+w_2)^*v \subseteq L$ .

— holf

@holf yours does not seem to work for

a^{*} b^{*}

$a^*b^*$

— Denis