Wie kann man beweisen, dass eine Sprache kontextfrei ist?

26

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.

DW
quelle
Gestatten Sie mir, meine übliche Anmerkung zu hinterlassen: Wenn Sie eine kontextfreie Grammatik für die jeweilige Sprache bereitstellen, benötigen Sie einen Korrektheitsnachweis, der den Ansatz etwas unhandlich machen kann.
Raphael
Um dies zu einer richtigen Referenzfrage zu machen, die wir an problematische Dumper werfen können, können Sie eine Antwort hinzufügen, um Grammatiken und Automaten zu finden, vielleicht mit jeweils einem Beispiel? Vielen Dank!
Raphael
Beachten Sie, dass Rick Decker und Babou, bis das Material hierher verschoben wurde, einige typische kontextfreie Redewendungen in einer doppelten Frage gesammelt haben .
Raphael

Antworten:

13

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 :

  1. Verkettung: Wenn Sie die Sprache in zwei aufeinander folgende Teile aufteilen können, verwenden Sie diese ProduktionSS1S2

  2. Vereinigung: in disjunkte Teile aufgeteiltSS1S2

  3. Iteration: SS1Sε

Beispiel 1

Hier ein Beispiel für die Verschachtelung (Danke Raphael).

L={bkal(bc)manbok,l,m,n,oN,ko,2l=n,m2}

Ersetzen Sie durch 2 l . Wir können jetzt n Bedingungen fallen lassen.n2ln

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 + okOk>O oder k<OOk>Ok>Ok=s+O und wobei s eine neue Variable ist. Ersetze k durch s + o .s>0sks+O

L1={bs+Oeinl(bc)mein2lbOl,m,O,sN,s>0,m2}

Einige einfache Änderungen.

L1={bbsboalbcbc(bc)m(aa)lbol,m,o,sN}

Jetzt sehen wir die Verschachtelungsstruktur und beginnen mit dem Aufbau einer Grammatik.

S1TV , , U b U ε (siehe: Verkettung und Iteration hier)TbUUbUε

(wir erzeugenbeidseitig o b )VbVbWo b

WaWaaX

, Y b c b c , Z b c Z εXY.ZYbcbcZbcZε

Beispiel 2

K={akblcml=m+k}

Ein erstes "offensichtliches" Umschreiben.

K={akbm+kcmm,k0}={akbmbkcmm,k0}

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,mm+k=k+m

K={akbk+mcmm,k0}={akbkbmcmm,k0}

mit Produktionen , X a X bSXY , Y b Y c | & egr;XaXbεYbYcε

In ähnlicher Weise ist K={akblcmm=k+l}={akblclckk,l0}

mit Produktionen , X b X c | & egr;SaScXXbXcε


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

Hendrik Jan
quelle
11

Es gibt eine Charakterisierung der CFL, die nützlich sein kann, den Chomsky-Schützenberger-Satz .

Dyck-Sprache

Sei ein Alphabet. Wir definieren die Dyck -Sprache D T( T T ) * von T durch die kontextfreie Grammatik G = ( { S } , T T , δ , S ) mit δ gegeben ist durchTDT(TT^)TG=({S},TT^,δ,S)δ

.SaSa^Sε,aT

Chomsky-Schützenberger-Theorem

ist genau dann kontextfrei, wenn es solche gibtLΣ

  • ein alphabet ,T
  • eine reguläre Sprache undR(TT^)
  • Homomorphismus ψ:(TT^)Σ

damit

.L=ψ(DTR)

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={anbncmn,mN

  • (und kanonisch, T = { ] , }T={[,}T^={],} ),
  • undR=L([])
  • ψ(x)={a,x=[b,x= ]ε,x=c,x= 

der Satz impliziert, dass kontextfrei ist, insbesondere daL

.DTR={[n]nmmn,mN}

Beispiel 2

Zeigen Sie, dass L={bkal(bc)manbok,l,m,n,oN,ko,2l=n,m2} 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 gebrauchenabcbbko

  • ,T={[,,,<}
  • R=L(<+>+[++])L([++]<+>+)
  • ψ(x)={b,x{,,<}a,x=[aa,x= ]bc,x=ε,else

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=ψ(DTR)[]wDTR

DTR={<p>po[lmm]lop1,o0,l0,m2} {}

und damit

ψ(DTR)={bp+oal(bc)ma2lbop1,o0,l0,m2} {}={bkal(bc)manbok,l,m,n,oN,k>o,2l=n,m2} {}=L.

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 for DT 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 for R (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 suitable T, 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!

Raphael
quelle
It is undecidable whether any given language is context-free.
reinierpost