La deuxième langue se compose de toutes les cordes qui contiennent un certain nombre de`a suivi d`un nombre égal de`b`. Lemma: n`est pas régulier stratégie: preuve par contradiction preuve: Supposons qu`il est régulier; alors nous devons avoir un ensemble de cordes de la forme. Le cas où VWX n`a pas de 2 est similaire et nous donne aussi une contradiction. Nous montrons que pour tous les u, v, w, (1) – (3) ne tient pas. Donc, u = 0A, v = 0b, w = 0c1n où: a + b ≤ n, b ≥ 1, c ≥ 0, a + b + c = n mais, alors (3) échoue pour i = 0 uv0w = UW = 0a0c1n = 0A + C1N ∉ L, depuis a + c ≠ n. Ainsi, en pompant lemma, il existe u, v, w tel que (1)-(3) détiennent. Pompage Lemma est utilisé comme une preuve de l`irrégularité d`une langue. Pompage lemma, ici aussi, est utilisé comme un outil pour prouver qu`une langue n`est pas CFL. Ainsi, L n`est pas sans contexte. Supposons que L est régulier, puis par pompage Lemma les règles mentionnées ci-dessus suivent. Nous montrons que pour tous les u, v, w, x, y (1) – (3) ne tiennent pas.

Pompage Lemma pour les langues sans contexte (CFL) le lemme de pompage pour la CFL indique que pour toute langue libre de contexte L, il est possible de trouver deux sous-chaînes qui peuvent être «pompées» un nombre quelconque de fois et qui sont toujours dans la même langue. C`est, si le pompage Lemma détient, cela ne signifie pas que la langue est régulière. La première langue est régulière, puisqu`elle ne contient qu`un nombre fini de chaînes. Maintenant, laissez x L et | x | ≥ n. L`opposé de cela peut ne pas toujours être vrai. Prouvons, L012 = {0n1n2n | n ≥ 0} n`est pas sans contexte. Ainsi, si une langue est régulière, elle satisfait toujours le pompage Lemma. Si (1) et (2) maintenez alors x = 0n1n = UVW avec | UV | ≤ n et | v | ≥ 1. Si (1) et (2) maintenez alors x = 0n1n2n = uvwxy avec | VWX | ≤ n et | VX | ≥ 1. S`il existe au moins une chaîne faite à partir de pompage qui n`est pas en L, alors L n`est sûrement pas régulier. Ainsi, en pompant lemma, il existe u, v, w, x, y tel que (1) – (3) Hold.

Supposons que L est sans contexte, puis par pompage lemma, les règles mentionnées ci-dessus suivent. Donc, UNH a un nombre égal de 0, 1 et 2 nous donne une contradiction. Par (2), VX contient un 1 ou un 2. Supposons que VWX n`a pas de 0. Langues régulières, et 2. Ainsi UNH a`n` 0 et UNH a moins que`n` 1 `s ou a moins que`n` 2 `s. Contexte – langues libres pompage Lemma pour les langues régulières pour toute langue normale L, il existe un entier n, de sorte que pour tous les x L avec | x | ≥ n, il existe u, v, w 2 Σ ∗, tels que x = UVW, et (1) | UV | ≤ n (2) | v | ≥ 1 (3) pour tous les i ≥ 0: uviw L. en termes simples, cela signifie que si une chaîne v est «pompée», i. La troisième langue est également régulière, car elle équivaut à l`expression régulière (a *) (b *). Maintenant, laissez x L et | x | ≥ n. Pour toute langue L, nous cassons ses cordes en cinq parties et la pompe deuxième et quatrième sous-chaîne.

Parce que, si une chaîne ne satisfait pas à ses conditions, alors la langue n`est pas CFL. Il y a deux lemmas de pompage, qui sont définis pour 1. Mais (3) nous dit que UNH = uv0wx0y L. Nous avons donc deux cas à considérer. Supposons qu`un tel sous-ensemble existe. Pour l`exemple ci-dessus, 0n1n est CFL, comme toute chaîne peut être le résultat d`un pompage à deux endroits, l`un pour 0 et l`autre pour 1. Ainsi, soit VWX n`a pas de 0, ou VWX n`a pas de 2. Il est à noter que nous ne pouvons tirer aucune conclusion du fait que). Par exemple, prouvons L01 = {0n1n | n ≥ 0} est irrégulier..