Contexte Langue libre Question (Lemme de pompage)

Question

Je sais que ce ne soit pas directement lié à la programmation, mais je me demandais si quelqu'un sait comment appliquer le lemme de pompage à l'épreuve suivante:

  

Montrer que L = {(a ^ n) (b ^ n) (c ^ m): n = m} est pas un langage algébrique

Je suis assez confiant avec l'application lemmes de pompage, mais celui-ci est vraiment me irking. Que pensez-vous?

Answer 1

Edit: je vous totalement menais la mauvaise voie. Voilà ce qui arrive lorsque je tente d'aider quand je ne l'ai pas complètement résolu le problème moi-même.

Lemme Ogden

Supposons que L est libre contexte. D'après le lemme d'Ogden, il existe un entier p qui a les propriétés suivantes:

d'une chaîne w L au moins p symboles long, où au moins p de ces symboles sont « marqués », w peut être représenté comme uvxyz, qui satisfont à:

1. x a au moins un symbole marqué,
2. soit u et v ont tous deux marqués des symboles ou Y et Z ont tous deux marqués des symboles,
3. vxy a au plus p symboles marqués et
4. u v ⁱ x y ⁱ z est en L pour i> = 0

C'est lemme d'Ogden. Maintenant, soit q un entier divisible par tout entier positif non supérieur à p. Soit w = a ^{p + q} b ^{p + q} c ^p . Marquez tous les c. Par le n ° 2, u ou v doit contenir au moins un c. Si l'u ou v contient tout autre symbole, puis # 4 échoue, si u et v doit contenir que c. Mais # 4 échoue lorsque i = q / | uv |. Nous savons q est divisible par | uv | parce que p> | uv | > 0, et q est divisible par tous les nombres entiers positifs inférieurs à p.

Notez que le lemme de Ogden se transforme en lemme de pompage lorsque vous marquez tous les symboles.

Pumping Lemma

Supposons que L est libre contexte. Par le lemme de pompage, il y a une longueur p (pas nécessairement le même que ci-dessus p) de telle sorte que tout mot w dans L peut être représentée comme uvxyz, où

1. | vxy | <= P,
2. | Vy | > = 1, et
3. u v ⁱ x y ⁱ z est en L pour i> = 0.

Etant donné un mot w dans L, soit m> n ou m

Supposons que m> n. (Notez que Λ désigne la chaîne vide).

• Soit u = a ⁿ b ⁿ c ^m-1
• Soit v = c
• Soit x = Λ
• Soit y = Λ
• Soit z = Λ

Supposons que n> m.

• Soit u = a ^n-1
• Soit v = a
• Soit x = Λ
• Soit y = b
• Soit z = b ^n-1 c ^m

Ceci démontre qu'aucune chaîne de L fournit un contre en utilisant le lemme de pompage à supposer que L est un contexte langage libre (même si elle est sensible au contexte).