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

11

Ich habe die folgende Sprache

{0i1j2k0ijk}

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 2 s) steht. Es könnte das v und x 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?uvwxy2vx

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
@ 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:

7

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 w = 0 p 1 p 2 p, was in der Sprache ist, und Sie "markieren" alle Nullen. Dann muss jede Faktorisierung w = u x y z v so sein, dass es in x oder z eine 0 gibt . Sie können auch x = a k und z = b m annehmen, da x x und z zp>0w=0p1p2pw=uxyzv0xzx=akz=bmxxzz muss Teilzeichenfolgen Ihrer Sprache sein.

  1. Wenn dann hat w = u x 2 y z 2 v mehr Nullen als Einsenz=0...0w=ux2yz2v

  2. Wenn und z = 1..1, dann hat w = u x 2 y z 2 v mehr Einsen als Zweien .x=0..0z=1..1w=ux2yz2v

  3. Wenn und z = 2..2, dann hat w = u x 2 y z 2 v mehr Nullen als Einsen .x=0..0z=2..2w=ux2yz2v

So ist kein Wort der Sprache. Daher ist es nicht kontextfrei.ux2yz2v

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
1
Ja, aber mit einem der pumpenden Deckspelzen können Sie das Wort wählen (und ich habe ): Ogdens Lemma soll für alle funktionieren. 0p1p2p
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
5

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 u v n w x n y auch in der Sprache vorkommt, auch wenn n = 0 istz=uvwxyuvnwxnyn=0 . Versuch das.

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

  1. p
  2. sp
  3. s=uvxyz|vxy|p|vy|1)
  4. You give an integer n0
  5. If uvnxynz 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 uvnxynz=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