Charakterisierung von

Es ist ein Standardnachweis in Automatenkursen, der für $L = \Sigma^\star$ und $|\Sigma| \ge 2$ dass $S(L) = \{ww : w \in L\}$ keine kontextfreie Sprache ist.

Es ist auch wahr , dass für jede endliche $L$ , $S(L)$ endlich ist (und daher ein CFL). Ich vermute, dass $L$ unendlich und regelmäßig ist nicht "ausreichend" für $S(L)$ ist keine CFL. Edit : was ist mit non-CFL $L$ ?

Gibt es eine Charakterisierung dessen, was dass keine CFL ist? $L$ $S(L)$

context-free Ryan
quelle

Wenn ich es richtig verstehe, ist die Frage , ob

einer regulären Sprache

kontextfrei ist oder nicht.

L

$L$

S (L)

$S(L)$

J.-E.

1. Können Sie uns mehr darüber erzählen, nach welcher Art von Charakterisierung Sie suchen? Suchen Sie einen Algorithmus, der mit

entscheidet, ob

kontextfrei ist? Suchen Sie nach Bedingungen für

, die ausreichen, um sicherzustellen, dass

kontextfrei ist? Wie soll eine Charakterisierung aussehen? 2. Wenn Sie nach ein paar Tagen keine Antwort erhalten und dies lieber auf CSTheory.SE sehen möchten, können Sie den Moderator darauf hinweisen und die Migration veranlassen.

L

$L$

S (L)

$S(L)$

L

$L$

S (L)

$S(L)$

@ DW 1. Entweder wäre in Ordnung, aber ich würde ausreichende Bedingungen bevorzugen. 2. Danke für den Tipp!

Ryan

@ Ryan gerade genügend Bedingungen? Nun, hier sind ein paar: (a) L ist regulär und für jedes

ist

(b) L ist CF und für alle

ist

entweder leer oder gleich

. Diese sind aber definitiv nicht notwendig. Wenn Sie hier keine Antworten erhalten, verschieben Sie die Frage bitte nach cstheory. Ich bin sehr gespannt auf notwendige und ausreichende Bedingungen!

w

$w$

L

$L$

w = w^{R}

$w = w^R$

n

$n$

L \cap Σ^{n}

$L \cap \Sigma^{n}$

Σ^{n}

$\Sigma^{n}$

Aelguindy

Unendliches und regelmäßiges

ist in der Tat nicht ausreichend für

nicht CF. Wenn

dann ist

was regulär ist, daher 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

Eher ein erweiterter Kommentar mit einer Vermutung, aber hier ist eine Bedingung, die das Problem zu erfassen scheint, im Kontext von regulärem für kontextfrei zu sein. $L$ $S(L)$

Bedingung In der minimalen DFA für enthält jeder akzeptierende Pfad höchstens eine Schleife. $A$ $L$

Ausnahme: Zwei Schleifen sind zulässig, wenn ihre Bezeichnungen und die Bezeichnung des Präfixes vor der ersten Schleife alle pendeln und das Suffix nach der zweiten Schleife leer ist. Zum Beispiel ist ok. $aa^*b(aa)^*$

Erinnern Sie sich, dass zwei Wörter und pendeln, wenn sie Potenzen desselben Wortes . Wir können annehmen, dass das Suffix leer ist, da es nicht leer sein darf und mit dem Label der zweiten Schleife in einem DFA pendelt. $u$ $v$ $t$

Ausreichend Angenommen, Sie erstellen einen PDA für indem Sie jedes Akzeptanzmuster von wobei eine einfache Schleife bezeichnet. Wir wollen Wörter der Form akzeptieren . Wir lesen , drücken ein Symbol für jedes Vorkommen von , lesen , dann platzieren wir ein Symbol für jedes Vorkommen von und lesen schließlich . $L$ $xuy$ $A$ $u$ $xu^nyxu^ny$ $x$ $u$ $yx$ $u$ $y$

Wenn wir uns in diesem Fall in der Ausnahme befinden, hat ein grundlegender Akzeptanzpfad die Form wobei die Beschriftungen der Schleifen sind. Wir akzeptieren Wörter der Form , aber unter der Annahme ( pendeln) ist es dasselbe wie , was kann von einem PDA erledigt werden: Taste drücken $xuyv$ $u,v$ $xu^n y v^m xu^n y v^m$ $x,u,v$ $u^nxyu^n v^mxyv^m$ $n$ mal (für Vorkommen von ), lese , pop mal, drücke mal (für ), lese , pop mal. $u$ $xy$ $n$ $m$ $v$ $xy$ $m$

Der endgültige PDA ist die Vereinigung der PDAs für jedes Muster.

Notwendig (Handwinken) Wenn es einen Pfad mit zwei Schleifen gibt, müssen Sie sich auch im einfachsten Fall, in dem Sie eine als die andere nehmen müssen (z. B. ), daran erinnern, wie oft jede genommen wird, aber an die Stapelstruktur verhindert, dass Sie sie in der gleichen Reihenfolge wiederholen. Beachten Sie, dass die Tatsache, dass der DFA minimal ist, bei der Charakterisierung wichtig ist, um die Verwendung von zwei Schleifen zu vermeiden, wenn eine ausreichen könnte. $a^*b^*$

Im Moment ist der notwendige Teil nur eine Vermutung und es könnten weitere Ausnahmen erforderlich sein, um die genaue Bedingung zu erhalten. Ich würde mich für Gegenbeispiele interessieren.

Denis
quelle

"und dann w noch einmal lesen, ein Symbol für jede Schleife platzen lassen, die beim zweiten Auftreten des Wortes genommen wird" - aber es gibt unendlich viele solcher

! Es sei denn, ich lese dein Argument falsch.

w

$w$

Ryan

@Ryan Die Anzahl der "Muster" xuy, in denen u eine Schleife beschriftet, ist endlich, sodass wir raten können, welche wir lesen.

Denis

Ich habe bearbeitet, um diesen Teil zu klären.

Denis

Die Bedingung ähnelt mir einer anderen, an die ich gedacht habe: S (L) ist kontextfrei, wenn es keine Wörter

, so dass

und

keine Präfixe voneinander sind und

u, v, w_{1}, w_{2}

$u,v,w_1,w_2$

w_{1}

$w_1$

w_{2}

$w_2$

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

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

Feiertag

@holf Ihr scheint nicht zu Arbeit für

a^{*} b^{*}

$a^*b^*$

Denis

Charakterisierung von

Antworten: