Es gibt verschiedene Möglichkeiten zu zeigen, dass eine Sprache nicht kontextfrei ist. Die häufigsten Methoden stützen sich auf den Nachweis, dass die Sprache gegen Eigenschaften verstößt, die kontextfreien Sprachen (CFLs) inhärent sind:

1. Pumpen Lemma für kontextfreie Sprachen: Dies ist die am weitesten verbreitete Technik. Das pumpende Lemma gibt an, dass es für jede CFL L eine konstante * p * (die Pumplänge) gibt, so dass jede Saite * w * in l mit Länge | w | ≥ *p *kann als *uvxyz *geschrieben werden, wo:

* | vxy | ≤ *p *

* | vy | ≥ 1

* * uv ⁱ xy ⁱ z* ∈ L für alle* i* ≥ 0

Um zu beweisen, dass eine Sprache mit dem Pumping Lemma * nicht * kontextfrei ist:

1. Angenommen: Angenommen, die Sprache * l * ist aus Gründen des Widerspruchs kontextfrei.

2. Wählen Sie eine Zeichenfolge: Wählen Sie eine Zeichenfolge *W *in *l *mit Länge mindestens die Pumplänge *p *(Sie müssen häufig strategisch *w *wählen).

3. Pumpen Sie die Zeichenfolge: Versuchen Sie, * w * in * uvxyz * zu zersetzen und die Bedingungen des Lemmas zu erfüllen.

4. einen Widerspruch finden: Zeigen Sie das für einige *i *, *uv ⁱ xy ⁱ z*ist*nicht*in*l*. Dies widerspricht dem pumpenden Lemma und beweist, dass die ursprüngliche Annahme (dass * l * kontextfrei ist) falsch sein.

Beispiel: Betrachten wir die Sprache l ={a ⁿ b n C ⁿ | n ≥ 0}. Verwenden des pumpenden Lemma:

1. Angenommen: L ist kontextfrei.

2. Wählen Sie eine Zeichenfolge: Sei * w * =a ^p b p C ^p (wo * p * die Pumplänge ist).

3. Pumpen Sie die Zeichenfolge: Egal wie Sie sich in *uvxyz *zersetzen, das Pumpen verstößt zwangsläufig gegen die A b n C ⁿ Struktur. Wenn * vxy * beispielsweise nur 'A enthält, erhöht das Pumpen die Anzahl der' a, ohne die Anzahl der 'Bs und' C zu erhöhen. Ähnliche Probleme treten auf, wenn * vxy * nur 'bs oder' c oder eine Mischung enthält, die nicht das gleiche Verhältnis beibehält.

4. Widerspruch: Daher gibt es ein *i *so, dass *uv ⁱ xy ⁱ Z* ∉ L, widerlegt dem pumpenden Lemma. Somit ist L nicht kontextfrei.

2. Verschlusseigenschaften: Kontextfreie Sprachen werden unter bestimmten Operationen geschlossen (Union, Verkettung, Kleene Star, Schnittpunkt mit einer regulären Sprache). Wenn Sie zeigen können, dass eine Sprache unter einem dieser Operationen * nicht * geschlossen ist, kann sie nicht kontextfrei sein. Diese Methode wird weniger häufig für direkte Beweise als das pumpende Lemma verwendet, kann jedoch in Kombination mit anderen Techniken hilfreich sein.

3. Ogdens Lemma: Dies ist eine leistungsstärkere Version des pumpenden Lemma, sodass Sie markierte Positionen innerhalb der Zeichenfolge *W *auswählen können. Es ist nützlich für Sprachen, in denen das einfache pumpende Lemma schwer zu bewerben ist.

4. Parikhs Theorem: Dieser Satz bezieht sich auf die Anzahl der Vorkommen jedes Symbols in Strings einer Sprache. Obwohl es nicht direkt verwendet wird, um eine Sprache * nicht kontextfrei zu beweisen, kann dies manchmal dazu beitragen, dass die Struktur einer Sprache mit den von CFLs auferlegten Einschränkungen unvereinbar ist. Es wird oft in Verbindung mit anderen Techniken verwendet.

Zusammenfassend ist das Pumping-Lemma die häufigste und allgemein wirksamste Methode, um zu beweisen, dass eine Sprache nicht kontextfrei ist. Die Auswahl der Methode hängt jedoch von der Struktur der spezifischen Sprache und der Leichtigkeit ab, mit der jede Technik angewendet werden kann. Ogdens Lemma bietet bei Bedarf mehr Strom, und Verschlusseigenschaften können zusätzliche Beweise liefern.