Es gibt viele Techniken , um zu beweisen , dass eine Sprache ist nicht kontextfrei, aber wie ich beweisen , dass eine Sprache ist kontextfrei?
Welche Techniken gibt es, um dies zu beweisen? Offensichtlich besteht eine Möglichkeit darin, eine kontextfreie Grammatik für die Sprache zu präsentieren. Gibt es systematische Techniken, um eine kontextfreie Grammatik für eine bestimmte Sprache zu finden?
Für reguläre Sprachen gibt es systematische Möglichkeiten , einen regulären Grammatik- / Finite-State-Automaten abzuleiten: Zum Beispiel bietet das Myhill-Nerode-Theorem eine Möglichkeit. Gibt es eine entsprechende Technik für kontextfreie Sprachen?
Meine Motivation ist es (hoffentlich), eine Referenzfrage zu erstellen, die eine Liste von Techniken enthält, die oft hilfreich sind, um zu beweisen, dass eine bestimmte Sprache kontextfrei ist. Da wir hier viele Fragen haben, bei denen es sich um Sonderfälle handelt, wäre es schön, wenn wir den allgemeinen Ansatz oder die allgemeinen Techniken dokumentieren könnten, die man anwenden kann, wenn man sich solchen Problemen stellt.
Antworten:
Ein praktischer Ansatz, der in vielen Beispielen funktioniert (aber ich weiß nicht immer), besteht darin, die Verschachtelungsstruktur der Zeichenfolgen in der Sprache zu finden. "Verschachtelte Abhängigkeiten" müssen gleichzeitig in verschiedenen Teilen des Strings generiert werden.
Wir haben auch die Basis-Toolbox :
Verkettung: Wenn Sie die Sprache in zwei aufeinander folgende Teile aufteilen können, verwenden Sie diese ProduktionS→S1S2
Vereinigung: in disjunkte Teile aufgeteiltS→S1∣S2
Iteration:S→S1S∣ε
Beispiel 1
Hier ein Beispiel für die Verschachtelung (Danke Raphael).
Ersetzen Sie durch 2 l . Wir können jetzt n Bedingungen fallen lassen.n 2l n
Ersetze durch k > o oder k < o (verwirrt? O ist 'oh' nicht 'null'). Werkzeuge für die Vereinigung anwenden. Wir arbeiten hier mit k > o . Auch k > o wenn k = s + ok≠o k > o oder k < o O k > o k > o k = s + o und wobei s eine neue Variable ist. Ersetze k durch s + o .s > 0 s k s + o
Einige einfache Änderungen.
Jetzt sehen wir die Verschachtelungsstruktur und beginnen mit dem Aufbau einer Grammatik.
(wir erzeugenbeidseitig o b )V→bVb∣W o b
, Y → b c b c , Z → b c Z ∣ εX→ YZ Y.→bcbc Z→bcZ∣ε
Beispiel 2
Ein erstes "offensichtliches" Umschreiben.
In der Sprachwissenschaft nennt man dies "Kreuz-Serien-Abhängigkeit": die Verschachtelung weist (normalerweise) stark auf Nichtkontextfreiheit hin. Natürlich ist m + k = k + m und wir sind gerettet.k,m,k,m m+k=k+m
mit Produktionen , X → a X bS→XY , Y → b Y c | & egr;X→aXb∣ε Y→bYc∣ε
In ähnlicher Weise istK′={akblcm∣m=k+l}={akblclck∣k,l≥0}
mit Produktionen , X → b X c | & egr;S→aSc∣X X→bXc∣ε
Letzter Kommentar: Diese Techniken helfen Ihnen dabei, eine kontextfreie Grammatik für Kandidaten zu finden, die Ihre Sprache hoffentlich erkennt. Möglicherweise ist noch ein Korrektheitsnachweis erforderlich, um sicherzustellen, dass die Grammatik Ihre Sprache wirklich erkennt (nicht mehr und nicht weniger).
quelle
Es gibt eine Charakterisierung der CFL, die nützlich sein kann, den Chomsky-Schützenberger-Satz .
Dyck-Sprache
Chomsky-Schützenberger-Theorem
Beachten Sie, dass der Homomorphismus auf Wörter (Symbol für Symbol) und dann auf Sprachen (Wort für Wort) ausgedehnt wird.
Beispiel
Betrachten wir . MitL={anbncm∣n,m∈N
der Satz impliziert, dass kontextfrei ist, insbesondere daL
.DT∩R={[n]n⟨m⟩m∣n,m∈N}
Beispiel 2
Zeigen Sie, dassL={bkal(bc)manbo∣k,l,m,n,o∈N,k≠o,2l=n,m≥2} kontextfrei ist.
Hier müssen wir eine Art von Klammern für , eine für b c , eine für b und andere verwendet , um die zu modellieren b dass Ursache k ≠ o . Wir gebrauchena bc b b k≠o
und wende den Satz an. Um zu sehen, dass , brauchen wir nicht mehr als die Tatsache, dass übereinstimmende Symbole (z. B. [ und ] ) in jedem w ∈ D T gleich häufig vorkommen müssen . Wenn wir diese Einschränkung zu den regulären Ausdrücken hinzufügen, durch die wir R definiert haben , erhalten wirL=ψ(DT∩R) [ ] w∈DT R
und damit
To grammars and automata
If we want to have an automaton or grammar in the end, we have some more work ahead of us.
Towards an automaton, construct the NPDA forDT and an NFA for R . The former is standard and we have algorithms for the latter, provided the language is given in a suitable representation (see also here). Intersection both is another standard construction and ψ can be applied to every transition individually.
Towards a grammar, build one forR (again, should be standard), take the one for DT and intersect them. Then apply ψ to the rule set (symbol for symbol).
Arguably, this is easy since algorithmic; the complexity lies in finding suitableT , R and ψ . I don't know if this approach is (often) simpler than constructing PDA/grammars directly but it may allow to focus on the important features of the language at hand. Try for yourself!
quelle