Beispiel für eine nicht-kontextfreie Sprache, die trotzdem gepumpt werden kann?

Das klassische Beispiel ist . Wise zeigt in seiner Arbeit Ein starkes Pumplemma für kontextfreie Sprachen , das weder mit dem Bar-Hillel-Pumplemma noch mit dem Satz von Parikh (der besagt, dass die Menge der Wortlängen in einer kontextfreien Sprache semi-linear ist) bewiesen werden kann dass nicht kontextfrei ist. Andere Tricks wie das Überschneiden mit einer normalen Sprache helfen ebenfalls nicht. (Ogdens Lemma, eine Verallgemeinerung des Bar-Hillel-Pumplemmas, beweist, dass $L = \{ a^i b^j c^k : i,j,k \text{ all different} \}$ $L$ $L$ nicht kontextfrei ist.) Er hat auch eine alternative Pump Lemma liefert das ist äquivalent (für berechenbare Sprachen) zu den inhaltlichen Mahlgrad und verwendet es zu beweisen , dass nicht kontextfrei. $L$

Das Pump-Lemma von Wise besagt, dass eine Sprache nur dann kontextfrei ist, wenn es eine (uneingeschränkte) Grammatik die und eine ganze Zahl so dass, wann immer eine "sententiale Form" (so können Nicht-Terminals enthalten). die Länge , wir können schreiben wobei nicht leer sind, $L$ $G$ $L$ $k$ $G$ $s$ $s$ $|s| > k$ $s = uvxyz$ $x,vy$ $|vxy| \leq k$ Und es ist ein nicht-terminale , so dass erzeugt und erzeugt sowohl und . $A$ $G$ $uAz$ $A$ $vAy$ $x$

Durch wiederholtes Anwenden der Bedingung im Lemma kann Wise nachweisen, dass nicht kontextfrei ist, die Details jedoch etwas kompliziert sind. Er gibt auch eine noch kompliziertere äquivalente Bedingung an und verwendet sie, um zu beweisen, dass die Sprache nicht als endliche Schnittmenge von kontextfreien Sprachen geschrieben werden kann. $L$ $\{ a^n b a^{nm} : n,m > 0 \}$

Wenn Sie nicht auf Wises Papier zugreifen können (es befindet sich hinter einer Paywall), gibt es eine maschinengeschriebene Version, die als technischer Bericht der Indiana University herauskam.

Eine nicht kontextfreie Sprache, die die Pumpbedingung von Ogdens Deckspelze erfüllt, wird von Johnsonbaugh und Miller, Converse of Pumping Lemmas, angegeben und dort Boasson und Horvath, On languages, zugeschrieben, die Ogdens Deckspelze erfüllen . Die fragliche Sprache ist Wir können schreiben

\begin{aligned} L^{'} & = ⋃_{n \geq 1} (e^{+} a^{+} d^{+})^{n} (e^{+} b^{+} d^{+})^{n} (e^{+} c^{+} d^{+})^{n} \\ \cup (a + b + c + d) Σ^{*} \cup Σ^{*} (a + b + c + e) \cup Σ^{*} (e d + d (a + b + c) + (a + b + c) e) Σ^{*} . \end{aligned}

$\begin{align*} L' &= \bigcup_{n \geq 1} (e^+a^+d^+)^n(e^+b^+d^+)^n(e^+c^+d^+)^n \\ &\cup (a+b+c+d)\Sigma^* \cup \Sigma^*(a+b+c+e) \cup \Sigma^*(ed+d(a+b+c)+(a+b+c)e)\Sigma^*. \end{align*}$

, entsprechend den zwei verschiedenen Linien. Man beachte, dass

und dass

regulär ist. Ogdens Lemma kann verwendet werden, um zu beweisen, dass

nicht kontextfrei ist, und

, aber es kann nicht direkt verwendetwerden, umzu zeigen, dass

nicht kontextfrei ist.

L^{'} = L_{1} \cup L_{2}

$L' = L_1 \cup L_2$

L_{1} \cap L_{2} = \emptyset

$L_1 \cap L_2 = \emptyset$

L_{2}

$L_2$

L_{1}

$L_1$

L^{'}

$L'$

L^{'}

$L'$

Yuval Filmus
quelle

Muss es nicht mindestens eine Produktion sein, die so

aussieht

Ganz allgemein: Muss ein Nichtterminal B nicht Teil einer von A ableitbaren Sententialform sein, sodass B-> sententialForm1.B.sententialfrom2 eine Produktion von G ist? Wie wäre es sonst sicher, dass ein Wort von a Beliebige Länge kann von A gepumpt werden.

user2329564

Ich verstehe nicht warum, wir haben eine Produktion

, die dem Pumpen entspricht. Zum Beispiel zu sofort das Pump Lemma da

A \Rightarrow^{+} v A y

$A \Rightarrow^+ vAy$

S \Rightarrow^{*} u A z \Rightarrow^{*} u v^{i} A y^{i} z \Rightarrow^{*} u v^{i} x y^{i} z

$S \Rightarrow^* uAz \Rightarrow^* uv^iAy^iz \Rightarrow^* uv^ixy^iz$

Yuval Filmus

Klingt nach einer schönen Ergänzung zu unserer Referenz .

Raphael

Eine andere Sache, die dort fehlt, ist die Schließung unter "inverse gsm-Zuordnungen", siehe planetmath.org/generalizedsequentialmachine . Vielleicht füge ich diese irgendwann hinzu.

Yuval Filmus

Beispiel für eine nicht-kontextfreie Sprache, die trotzdem gepumpt werden kann?

Antworten: