Lema del bombament

En la teoria de llenguatges formals de la teoria de la computació, el lema de bombament estableix que en un llenguatge, qualsevol cadena de caràcters d'almenys una certa longitud (anomenada longitud de bombament), conté una secció que pot ser eliminada o repetida qualsevol nombre de vegades, amb la cadena resultant pertanyent a aquest llenguatge. La prova d'aquest lema requereix arguments de comptatge, com els del principi del colomar.

Els dos exemples més importants són el lema de bombament per a llenguatges regulars i el lema del bombament per gramàtiques independents del context. El lema d'Ogden és un segon lema de bombament, més fort, per llenguatges lliures de context.

Definició formal

Si A és un llenguatge regular, llavors hi ha un natural N tal que tota la paraula del llenguatge w amb longitud ≥ N pot ser descomposta en tres parts, w = xyz, que compleixen la següent condicions:

1. ∣xy∣ ≤ N
2. ∣y∣ > 0
3. ∀i xyⁱz ∈ A

Si trobem una paraula del llenguatge amb una longitud ≥ N i que no es pugui descompondre en tres parts, xyz, que compleixin les tres condicions, llavors, podem dir que el llenguatge no és regular.

Exemple

Demostra que el següent llenguatge no és regular: L = {a²ⁿbⁿ | n ≥ 0}

Suposem que el llenguatge és regular, si ho és, llavors com que és infinit complirà el lema del bombament. Sigui n ∈ N la constant del lema del bombament per L. Escollim una paraula que pertanyi al llenguatge, w = a²ⁿbⁿ, tenim que w ∈ L i ∣w∣ > 3n, per tant ∣w∣ ≥ n.

Partim la paraula en tres parts, tenint en compte les condicions:

1. w = xyz
2. ∣y∣ > 0
3. ∣xy∣ ≤ n

Per tant:

1. x = aⁱ
2. y = a^j, on j > 0
3. z = a^2n-i-jbⁿ

La paraula w, que estava formada per xyz, ara veiem que serà: w = aⁱa^ja^2n-i-jbⁿ. El següent pas consisteix a buscar una constant, per la qual la paraula ja no sigui bombajable. Si agafem la constant k = 2 i bombem les x, y i z de la paraula w tenim que:

w = xyz = aⁱa^2ja^2n-i-jbⁿ = a^2n+jbⁿ

I com que j > 0, tenim que w = a^2n+jbⁿ és una paraula que no pertany al llenguatge donat que tenim més del doble de a's que de b's. Com que hem arribat a una contradicció podem afirmar que el llenguatge L no és regular

Referències

• Michael Sipser. Introduction to the Theory of Computation. PWS Publishing, 1997. ISBN 0-534-94728-X.