5.10. Iterációs lemma reguláris nyelvekre

A következő tétel egy hatékony eszköz lehet annak megmutatására, hogy valamely nyelv nem reguláris. A tételt iterációs- vagy pumpáló lemma néven szokás emlegetni.

31. Tétel. Legyen L reguláris nyelv. Ekkor létezik az L- hez olyan n konstans, hogy ha z egy n- nél hosszabb L- beli szó, akkor alkalmas u, v, w szavakra teljesülnek a következők: z=u v w, |u v| ≤ n, |v|>0, továbbá tetszőleges nemnegatív i- re u v i wL.

Bizonyítás. Legyen L reguláris, ekkor legyen F A=(Q, T, q 0, d, F) minimális determinisztikus automata úgy, hogy L(F A)=L. Legyen n=|Q|+1. Ekkor bármely zL, |z|>n szót is tekintjük az automata bemenetének, biztosan van olyan állapot, amelyet F A a szó elfogadása során legalább kétszer érint, sőt az első n lépés alatt is lennie kell ilyen q állapotnak. Bontsuk fel z szót ennek megfelelően: legyen u a z olyan prefixe amely a kezdőállapotból (először) q- ba viszi az automatát, v pedig olyan, amely az automatát q- ból indulva ugyancsak q- ba viszi (másodszor). Ekkor |u v| ≤ n fennáll. Mivel a q két előfordulása közt az automatának legalább egy lépése történt, azaz legalább egy input betűt beolvasott |v|>0 is teljesül.

Amennyiben az automata a q állapotból indulva a w szót olvassa, elfogadó állapotba kerül. Ennek megfelelően az u w inputot F A elfogadja. Hasonlóan minden u v i w ( i>0) alakú szót is elfogad, hiszen u a q állapotba viszi, ahonnan indulva a v i szavak elolvasása után ugyancsak q állapotba jutunk, végül innen w egy végállapotba vezet.

A tétel igazolását ezzel befejeztük. ∎

5.48. példa - Iterációs lemma alkalmazása

Legyen L={a m b m |m>0}. Felhasználva a reguláris pumpáló lemmát, kimutatjuk, hogy ez a nyelv nem reguláris. Tegyük fel hogy az, s jelöljön n egy konstanst, mely mellett L kielégíti a reguláris pumpáló lemma tulajdonságait. Ilyen n- t viszont nem fogunk találni, hiszen az a n b n szó minden olyan u v w felbontására, melyre |u v| ≤ n és |v|>0, azt kapjuk, hogy u w=a n-|v| b n , azaz u wL. (Hasonlóan, minden i>1- re u v i w=a n+(i-1)|v| b n L.) Ezt az ellentmondást csak az indirekt feltevésünk hamissága okozhatja, tehát L nem reguláris. ★


Egyébként a példabeli nyelv a G=({S}, {a, b}, S, {Sa S b, S → a b}) lineáris nyelvtannal generálható.