Wie kann man zeigen, dass L = L (G)?

Das Spezifizieren von formalen Sprachen durch die Angabe formaler Grammatiken ist eine häufige Aufgabe: Wir brauchen Grammatiken, um Sprachen nicht nur zu beschreiben, sondern auch zu analysieren oder sogar Wissenschaft zu betreiben . In allen Fällen ist es wichtig, dass die vorliegende Grammatik korrekt ist, dh genau die gewünschten Wörter generiert.

Wir können oft auf hoher Ebene darüber streiten, warum die Grammatik eine angemessene Darstellung der gewünschten Sprache ist, ohne einen formalen Beweis. Aber was ist, wenn wir Zweifel haben oder aus irgendeinem Grund einen formellen Beweis benötigen? Welche Techniken können wir anwenden?

^{Dies soll eine Referenzfrage werden . Achten Sie daher darauf, allgemeine, didaktisch aufbereitete Antworten zu geben, die an mindestens einem Beispiel illustriert sind, aber dennoch viele Situationen abdecken. Vielen Dank!}

Grammatiken sind von Natur aus rekursive Objekte, daher liegt die Antwort auf der Hand: durch Induktion. Das heißt, die Einzelheiten sind oft schwierig, richtig zu machen. In der Folge werde ich eine Technik beschreiben, die es ermöglicht, viele Grammatikkorrektheitsnachweise auf mechanische Schritte zu reduzieren, vorausgesetzt, eine kreative Vorverarbeitung wird durchgeführt. $\newcommand{\lang}[1]{\mathcal{L}(#1)} \newcommand{\sent}[1]{\vartheta(#1)} \newcommand{\derive}{\mathbin{\Rightarrow}} \newcommand{\derivestar}{\mathbin{\Rightarrow^*}} \newcommand{\nats}{\mathbb{N}}$

Die Grundidee ist, sich nicht auf Wörter der Grammatik und der Sprache zu beschränken; Es ist schwer, die Struktur der Grammatik auf diese Weise zu erfassen. Stattdessen streiten wir uns über die Menge der Sätze, die die Grammatik erzeugen kann. Darüber hinaus werden wir ein entmutigendes Beweisziel in viele kleine Ziele aufteilen, die leichter zu erreichen sind.

Lassen eine formale Grammatik mit Nonterminals , Klemmen , Regeln und Startsymbol . Wir bezeichnen mit der Satz von Sätzen , die von der abgeleitet werden kann gegeben , dh . Die von erzeugte Sprache ist . Angenommen, wir wollen zeigen, dass für einige .N T δ S ≤ N ≤ ( G ) S $G=(N,T,\delta,S)$$N$$T$$\delta$$S \in N$$\sent{G}$$S$$\delta$G L ( G ) = ϑ ( G ) ∩ T ∗ L = L ( G ) L ⊆ $\alpha \in \sent{G} \iff S \derivestar \alpha$$G$$\lang{G} = \sent{G} \cap T^*$$L = \lang{G}$$L \subseteq T^*$

Der Ansatz

So gehen wir vor. Wir definieren damit$M_1, \dots, M_k \subseteq (N \cup T)^*$

1. $\displaystyle \sent{G} = \bigcup_{i=1}^k M_i$ und
2. $\displaystyle T^* \cap \bigcup_{i=1}^k M_i = L$ .

Während 2. normalerweise per Definition des klar ist , erfordert 1. einige ernsthafte Arbeit. Die beiden Elemente zusammen bedeuten eindeutig wie gewünscht.L ( G ) = $M_i$$\lang{G} = L$

Zur Vereinfachung der Notation bezeichnen wir .$M = \bigcup_{i=1}^k M_i$

Der steinige Weg

Es gibt zwei Hauptschritte, um einen solchen Beweis durchzuführen.

• Wie finde (gutes) ? $M_i$
  Eine Strategie besteht darin, die Phasen zu untersuchen , in denen die Grammatik arbeitet. Nicht jede Grammatik ist dieser Idee zugänglich; Im Allgemeinen ist dies ein kreativer Schritt. Es hilft, wenn wir die Grammatik selbst definieren können. Mit etwas Erfahrung werden wir in der Lage sein, Grammatiken zu definieren, die sich mit diesem Ansatz besser handhaben lassen.

• Wie beweise ich 1.?
  Wie bei jeder Mengengleichheit gibt es zwei Richtungen.

  • $\sent{G} \subseteq M$ : (strukturelle) Induktion über die Produktionen von .$G$
  • M i$M \subseteq \sent{G}$ : Normalerweise eine Induktion von , beginnend mit der, die enthält .$M_i$$S$

Dies ist so spezifisch wie es nur geht; Die Details hängen von der jeweiligen Grammatik und Sprache ab.

Beispiel

Betrachten Sie die Sprache

$\qquad \displaystyle L = \{ a^n b^n c^m \mid n,m \in \nats \}$

und die Grammatik mit gegeben durch$G = (\{S,A\}, \{a,b,c\}, \delta, S)$$\delta$

$\qquad \begin{align} S &\to Sc \mid A \\ A &\to aAb \mid \varepsilon \end{align}$

für die wir zeigen wollen, dass . Welche Phasen durchläuft diese Grammatik? Nun, zuerst erzeugt es und dann . Dies informiert sofort unsere Wahl von , nämlichc m a n b n M $L = \lang{G}$$c^m$$a^n b^n$$M_i$

$\qquad \begin{align} M_0 &= \{Sc^m \mid m \in \nats \} \;, \\ M_1 &= \{ a^n A b^n c^m \mid m,n \in \nats \} \;, \\ M_2 &= \{ a^n b^n c^m \mid m,n \in \nats \} \;. \\ \end{align}$

Da und , ist Punkt 2. bereits . In Richtung 1. teilen wir den Beweis wie angekündigt in zwei Teile.M 0 ∩ T * = M 1 ∩ T * = $M_2 = L$$M_0 \cap T^* = M_1 \cap T^* = \emptyset$

$\mathbf{\sent{G} \subseteq M}$

Wir führen eine strukturelle Induktion nach den Regeln von .$G$

IA: Da , verankern wir erfolgreich.$S = Sc^0 \in M_0$

IH: Nehmen wir für einige Mengen von Sätzen dass wir auch .X ⊆ $X \subseteq \sent{G}$$X \subseteq M$

IS: Lassen Sie beliebig. Wir müssen zeigen, dass wir nicht verlassen , unabhängig davon, welche Form hat und welche Regel als Nächstes angewendet wird . Wir tun dies durch vollständige Fallunterscheidung. Aus der Induktionshypothese wissen wir, dass (genau) einer der folgenden Fälle zutrifft:α $\alpha \in X \subseteq \sent{G} \cap M$$\alpha$$M$

• w = S c m m ≤ N$w \in M_0$ , das heißt für einige . Es können zwei Regeln angewendet werden, die beide einen Satz in ableiten : $w = Sc^m$$m \in \nats$
  $M$
  • $Sc^m \derive Sc^{m+1} \in M_0$ und ab
  • $Sc^m \derive Ac^m = a^0Ab^0c^m \in M_1$ .
• w = a n A b n c m m , n ≤ $w \in M_1$ , dh für einige : $w = a^nAb^nc^m$$m,n \in \nats$
  • $w \derive a^{n+1}Ab^{n+1}c^m \in M_1$ und ab
  • $w \derive a^nb^nc^m \in M_2$ .
• w ∈ T $w \in M_3$ : seit sind keine weiteren Ableitungen möglich.$w \in T^*$

Da wir alle Fälle erfolgreich abgedeckt haben, ist die Einführung abgeschlossen.

$\mathbf{\sent{G} \supseteq M}$

Wir führen einen (einfachen) Beweis pro . Beachten Sie, wie wir die Beweise verketten, damit "später" mit dem "früheren" verankern kann .M i M $M_i$$M_i$$M_i$

• m S c 0 = S S → S $M_1$ : Wir führen eine Induktion über , verankern in und verwenden im Schritt .$m$$Sc^0 = S$$S \to Sc$
• m n A c m S ⇒ ∗ S c m ⇒ A c m A → a A $M_2$ : Wir fixieren auf einen beliebigen Wert und induzieren über . Wir verankern in und aus dem ersteren Beweis ab. Der Schritt geht über .$m$$n$$Ac^m$$S \derivestar Sc^m \derive Ac^m$$A \to aAb$
• $M_3$ : Für beliebige wir den ersteren Beweis für .$m,n \in \nats$$S \derivestar a^nAb^nc^m \derive a^nb^nc^m$

Damit ist die zweite Richtung des Beweises von 1 abgeschlossen, und wir sind fertig.

Wir können sehen, dass wir stark ausnutzen, dass die Grammatik linear ist . Für nichtlineare Grammatiken benötigen wir mit mehr als einem variablen Parameter (in den Beweisen), was hässlich werden kann. Wenn wir die Grammatik unter Kontrolle haben, lernen wir, sie einfach zu halten. Betrachten Sie als abschreckendes Beispiel diese Grammatik, die :$M_i$$G$

$\qquad \begin{align} S &\to aAbC \mid \varepsilon \\ A &\to aAb \mid \varepsilon \\ C &\to cC \mid \varepsilon \end{align}$

Übung

Gib eine Grammatik für

$\qquad L = \{ b^k a^l (bc)^m a^n b^o \mid k,l,m,n,o \in \nats, k \neq o, 2l = n, m \geq 2 \}$

und beweisen ihre Richtigkeit.

Wenn Sie Probleme haben, eine Grammatik:

Man betrachte mit Produktionen$G = (\{S,B_r,B_l,A,C\}, \{a,b,c\}, \delta, S)$

$\quad \begin{align} S &\to bSb \mid B_l \mid B_r \\ B_l &\to bB_l \mid bA \\ B_r &\to B_r b \mid Ab \\ A &\to aAaa \mid C \\ C &\to bcC \mid bcbc \end{align}$

und :$M_i$

$\quad\begin{align} M_0 &= \{ b^i S b^i \mid i \in \nats \} \\ M_1 &= \{ b^i B_l b^o \mid o \in \nats, i \geq o \} \\ M_2 &= \{ b^k B_r b^i \mid k \in \nats, i \geq k \} \\ M_3 &= \{ b^k a^i A a^{2i} b^o \mid k,o,i \in \nats, k \neq o \} \\ M_4 &= \{ b^k a^l (bc)^i C a^{2l} b^o \mid k,o,l,i \in \nats, k \neq o \} \\ M_5 &= L \end{align}$

Was ist mit nichtlinearen Grammatiken?

Das kennzeichnende Merkmal der Klasse der kontextfreien Sprachen ist die Dyck-Sprache : Im Wesentlichen kann jede kontextfreie Sprache als Schnittmenge einer Dyck-Sprache und einer regulären Sprache ausgedrückt werden. Leider ist die Dyck-Sprache nicht linear, das heißt, wir können keine Grammatik angeben, die inhärent für diesen Ansatz geeignet ist.

Wir können natürlich immer noch definieren und den Beweis , aber es ist mit verschachtelten Induktionen zwangsläufig schwieriger, und was nicht. Es gibt einen allgemeinen Weg, von dem ich weiß, dass er in gewissem Maße helfen kann. Wir ändern den Ansatz, um anzuzeigen, dass wir mindestens alle erforderlichen Wörter erzeugen und dass wir die richtige Anzahl von Wörtern (pro Länge) erzeugen. Formal zeigen wir das$M_i$

1. $\displaystyle \sent{G} \supseteq L$ und
2. n ∈ $\displaystyle |\lang{G} \cap T^n| = |L \cap T^n|$für alle .$n \in \nats$

Auf diese Weise können wir uns auf die "einfache" Richtung vom ursprünglichen Ansatz beschränken und die Struktur in der Sprache ausnutzen, ohne die überkomplizierten Merkmale der Grammatik zu beachten. Natürlich gibt es kein kostenloses Mittagessen: Wir haben die brandneue Aufgabe, die Wörter zu zählen, die für jedes generiert . Glücklicherweise ist dies oft nachvollziehbar. siehe hier und hier für Details¹. Einige Beispiele finden Sie in meiner Bachelorarbeit .n ∈ $G$ $n \in \nats$

Für mehrdeutige und nicht-kontextfreie Grammatiken, fürchte ich, sind wir wieder bei Ansatz eins und denken Großbuchstaben.

---

1. Wenn wir diese bestimmte Methode zum Zählen verwenden, erhalten wir als Bonus, dass die Grammatik eindeutig ist. Dies bedeutet wiederum auch, dass die Technik bei mehrdeutigen Grammatiken versagen muss, wie wir niemals beweisen können 2.