Context Free Sprachenfrage (Pumping Lemma)

Question

Ich weiß, das nicht direkt mit der Programmierung verwendet ist, aber ich frage mich, ob jemand wissen, wie das Pumping-Lemma auf den folgenden Beweis anwenden:

  

Zeigen Sie, dass L = {(a ^ n) (b ^ n) (c ^ m): n = m} ist keine kontextfreie Sprache

Ich bin ziemlich zuversichtlich, mit Pumpen Lemmata Anwendung, aber dies ist irking mir wirklich. Was denken Sie?

Answer 1

Edit: Ich war total führt Sie die falsche Spur zu kommen. Das ist, was passiert, wenn ich versuche zu helfen, wenn ich das Problem nicht vollständig selbst gelöst werden.

Ogdens Lemma

Es sei L ist kontextfrei. Durch Ogden Lemma existiert eine ganze Zahl p, die die folgenden Eigenschaften haben:

ein String w in L mindestens p Symbole lang gegeben, wobei zumindest p dieser Symbole „markiert“ werden, kann w als uvxyz dargestellt werden, für die gilt:

1. x hat mindestens eine markierte Symbol,
2. entweder u und v haben beide Symbole oder Y und Z beide Symbole markiert markiert,
3. vxy hat höchstens p Symbolen gekennzeichnet, und
4. u v ⁱ x y ⁱ z ist in L für i> = 0

Das ist Ogden Lemma. Nun lassen Sie q eine ganze Zahl teilbar durch jede positive ganze Zahl sein nicht mehr als p. Sei w = a ^{p + q} b ^{p + q} c ^p . Markieren Sie jeden c. Von # 2, u oder v, muss mindestens ein C enthalten. Wenn entweder U oder V ein anderes Symbol enthält, dann 4 # ausfällt, so u und v muss nur c enthalten. Aber dann # 4 schlägt fehl, wenn i q / = | uv |. Wir wissen, q teilbar durch | uv | weil p> | uv | > 0 und q durch alle positiven ganzen Zahlen kleiner als p teilbar ist.

Beachten Sie, dass Ogden Lemma abwechselnd in die Pump Lemma, wenn Sie alle Symbole markieren.

Pumping Lemma

Es sei L ist kontextfrei. Durch die Pump Lemmas, gibt es eine Länge p (nicht notwendigerweise die gleichen p wie oben), so daß jede Zeichenfolge in w L kann als uvxyz dargestellt werden, wobei

1. | vxy | <= P
2. | vy | > = 1 und
3. u v ⁱ x y ⁱ z ist in L für i> = 0 ist.

ein String w in L gegeben, entweder m> n oder m

Nehmen wir an, dass m> n. (Beachten Sie, dass Λ die leere Zeichenkette bezeichnet.)

• Sei u = a ⁿ b ⁿ C ^m-1
• Let v = c
• Let x = Λ
• Es sei y = Λ
• Sei z = Λ

Nehmen wir an, dass n> m.

• Es sei u = a ^n-1
• Sei v = a
• Let x = Λ
• Es sei y = b
• Let z = b ^n-1 C ^M

Dies zeigt, dass kein String aus L ein Gegenbeispiel mit dem Pumping-Lemma zu der Annahme, sieht vor, dass L eine kontextfreie Sprache ist (auch wenn es kontextsensitiv ist).