Charakterisierung von

16

Es ist ein Standardnachweis in Automatenkursen, der für L=Σ und |Σ|2 dass S(L)={ww:wL} 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 S ( L ) keine CFL ist?LS(L)

Ryan
quelle
Wenn ich es richtig verstehe, ist die Frage , ob S ( L ) in einer regulären Sprache kontextfrei ist oder nicht. LS(L)
J.-E.
2
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 S ( L ) kontextfrei ist? Suchen Sie nach Bedingungen für L , die ausreichen, um sicherzustellen, dass S ( L ) 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. LS(L)LS(L)
DW
@ DW 1. Entweder wäre in Ordnung, aber ich würde ausreichende Bedingungen bevorzugen. 2. Danke für den Tipp!
Ryan
1
@ Ryan gerade genügend Bedingungen? Nun, hier sind ein paar: (a) L ist regulär und für jedes in L ist w = w R (b) L ist CF und für alle n ist L Σ n entweder leer oder gleich Σ n . 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! wLw=wRnLΣnΣn
Aelguindy
Unendliches und regelmäßiges ist in der Tat nicht ausreichend für S ( L ) nicht CF. Wenn Σ = { a , b , c } , L = a ∗, dann ist S ( L ) = ( a a ) ∗, was regulär ist, daher CF. LS(L)Σ={a,b,c},L=aS(L)=(aa)
Chi

Antworten:

2

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 S ( L ) kontextfrei zu sein.LS(L)

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

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.aab(aa)

Erinnern Sie sich, dass zwei Wörter und v pendeln, wenn sie Potenzen desselben Wortes t sind . 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.uvt

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

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

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.ab

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
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 w 1 und w 2 keine Präfixe voneinander sind und u ( w 1 + w 2 ) * v L . u,v,w1,w2w1w2u(w1+w2)vL
Feiertag
@holf Ihr scheint nicht zu Arbeit für ab
Denis