Wie kann ich beweisen, dass diese Sprache nicht kontextfrei ist?

Ich habe die folgende Sprache

$\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$

Ich versuche herauszufinden, in welchen Chomsky-Sprachkurs es passt. Ich kann sehen, wie es mit einer kontextsensitiven Grammatik gemacht werden kann, also weiß ich, dass es zumindest kontextsensitiv ist. Es scheint, als wäre es nicht möglich, mit einer kontextfreien Grammatik zu arbeiten, aber ich habe ein Problem damit, dies zu beweisen.

Es scheint das Gabelpumpen-Lemma zu bestehen, denn wenn alle im dritten Teil eines Wortes (dem Abschnitt mit allen s) steht. Es könnte das und so oft pumpen, wie Sie möchten, und es würde in der Sprache bleiben. Wenn ich falsch liege, können Sie mir sagen, warum diese Sprache, wenn ich recht habe, immer noch nicht kontextfrei ist. Wie kann ich das beweisen? $uvwxy$ $2$ $v$ $x$

formal-languages context-free formal-grammars pumping-lemma justausr
quelle

Ich bin nicht sicher, wie ich es zu einem formalen Beweis machen soll, aber um sicherzustellen, dass i <= j <= k ist, ist Kontext erforderlich (der Wert der vorherigen Variablen).

Kevin

mögliches Duplikat von Wie kann man beweisen, dass eine Sprache nicht kontextfrei ist?

Raphael

@ Raphael, ich habe diesen Beitrag vor diesem gelesen und wusste nicht, wie ich ihn auf mein Beispiel anwenden soll, weil er abstrakt ist. Da die Beziehung jedes Zeichens> = die Anzahl der vorherigen Zeichen ist, konnte ich nicht sehen, wie das Uxyzv in das Wort aufgeteilt werden kann, um Ogdens Lemma zu verwenden. BlueMagister und jmad haben den anderen Beitrag erweitert, um mein Beispiel zu verdeutlichen.

Justausr

@ Raphael Ich bin nicht der Meinung, dass dies eine triviale Anwendung des allgemeinen Falls ist. Die Auswahl der zu verwendenden Methode und des Beispiels, auf das sie angewendet werden soll, ist nicht so einfach.

Gilles 'SO - hör auf böse zu sein'

Antworten:

Mit Ogdens Lemma können Sie das Pumpen an einigen Stellen erzwingen , indem Sie beispielsweise alle markieren.

Angenommen, es ist kontextfrei, dann gibt Ogdens Lemma Ihnen ein , Sie geben es was in der Sprache ist, und Sie "markieren" alle Nullen. Dann muss jede Faktorisierung so sein, dass es in oder eine gibt . Sie können auch und annehmen, da und $p>0$ $w=0^p1^p2^p$ $w=uxyzv$ $0$ $x$ $z$ $x=a^k$ $z=b^m$ $xx$ $zz$ muss Teilzeichenfolgen Ihrer Sprache sein.

Wenn dann hat mehr Nullen als Einsen $z=0...0$ $w=ux^2yz^2v$
Wenn und dann hat mehr als . $x=0..0$ $z=1..1$ $w=ux^2yz^2v$
Wenn und dann hat mehr als . $x=0..0$ $z=2..2$ $w=ux^2yz^2v$

So ist kein Wort der Sprache. Daher ist es nicht kontextfrei. $ux^2yz^2v$

Weitere Techniken finden Sie in der Diskussion: Wie kann man beweisen, dass eine Sprache nicht kontextfrei ist?

jmad
quelle

Ist das für dieselbe Sprache, die ich habe? Es scheint für die ähnliche Sprache zu sein, in der alle Einsen und Zweien der Null gleich lang sind. Diese Sprache hat die Anzahl von 2> = die Anzahl von 1> = die Anzahl von 0

justausr

Ja, aber mit einem der pumpenden Deckspelzen können Sie das Wort wählen (und ich habe

): Ogdens Lemma soll für alle funktionieren.

0^{p} 1^{p} 2^{p}

$0^p1^p2^p$

jmad

Gotcha, ich habe noch nie von Ogdens Lemma gehört, also muss ich mich darum kümmern. Hatte ich recht, dass es das Pump-Lemma nicht schafft?

Justausr

@justausr habe ich bis vor kurzem auch nicht (und dank der Diskussion, auf die ich mich bezog). Und ja, Sie hatten Recht: Das Pump-Lemma macht fast dasselbe, aber wenn Sie nicht wählen, wo Sie pumpen möchten, ist es hier nutzlos.

jmad

Das Pump-Lemma sollte Ihr Problem in Bezug auf den dritten Teil des Wortes lösen. Beachten Sie, dass beim Teilen von jede Kombination von auch in der Sprache vorkommt, auch wenn $z = uvwxy$ $uv^nwx^ny$ $n = 0$ . Versuch das.

EDIT: Wie jmad feststellt , ist das Pumping Lemma wie ein Spiel:

$p$

$s$ $p$

$s=uvxyz$ $|vxy|≤p$ $|vy|≥1$ )

You give an integer $n≥0$

If $uv^nxy^nz$ is not in $L$ , you win, $L$ is not context free.

So what you have to do is state a word, break down 3 into cases, and show that for each case you can find an $n$ such that the resulting word isn't in the language.

When you split $s=uvxyz$ , think of all the cases that $vxy$ can fall into. You note that if $vxy$ does not fall into the 2's, then it is easy to pump the 0's and 1's until they outnumber the 2's, and then you have a word that's not in the language. My suggestion is that, if $vxy$ falls into 2 territory, you can also make $v$ and $y$ disappear by setting $n=0$ , so $uv^nxy^nz = uxz$ . Then by eliminating a 2 you could arrive at a word that doesn't fall in the language.

Blue Magister
quelle

Are you saying put all of uvwxy in the section with 2's?

justausr

If it's given the right word. I'll elaborate in my answer.

Blue Magister

Here, try it now. I'm not sure if my pumping lemma is the same as your pumping lemma, so I appeal to Wikipedia.

Blue Magister