|
Pumpálási lemma reguláris nyelvekre
Állítás (Ez a lemma állítása)
Ha reguláris nyelv, akkor
egész szám, hogy
, ahol és
w minden
részszavára,
ahol
és , létezik -nek egy felosztása,
amelyben
és amely felbontásra minden
esetén.
Azaz: Ha egy reguláris nyelv, akkor létezik egy olyan hossz, aminél
hosszabb tetszőleges -beli szóban tetszőlegesen kiválasztva egy ennél a hossznál
nagyobb részszót igaz lesz a következő:
ezen részszóban van egy olyan rész valahol,
melyet tetszőlegesen sokszor megismételve (vagy elhagyva) még mindig -beli
szavakat kapunk.
Ennek a haszna:
Segítségével be lehet látni nyelvekről, hogy nem regulárisak.
Ez úgy megy, hogy ha megmutatjuk egy nyelvről, hogy van olyan szava,
amiben nem lehet a fentiek szerint pumpálni, akkor az tuti nem reguláris.
Vigyázat! Lehetnek olyan nyelvek, amiket lehet pumpálni, de mégsem regulárisak.
Vagyis ez a lemma csak a nem-reguláris nyelvek egy részét buktatja le.
Például az
nyelv nem reguláris, mert:
Tegyük fel, hogy az.
Vegyük az szót, ahol az az az , aminek létezését a
lemma garantálja és jelöljük ki -nek az részszót!
Ha ebben pumpálunk, akkor az -k száma megnő, de közben a -k száma
nem változik, azaz a kapott szó nem lesz eleme a nyelvnek.
Ezzel beláttuk, hogy a nyelv nem reguláris.
A lemma bizonyítása:
Ha az nyelv reguláris, akkor van egy olyan véges automata, ami
elfogadja őt. Legyen , azaz legyen az automata állapotainak
a száma.
Nézzük, hogy az automata milyen állapotokat érint,
onnantól kezdve, hogy rálép a
( ) szó első
betűjére, egészen odáig, hogy lelép az utolsóról is.
Ez összesen állapot:
.
Mivel ez több, mint amennyi állapota az automatának van, biztosan van
közöttük két egyforma. Ha
, akkor ez éppen azt jelenti, hogy
a szó olvasása során az automata az
részszó
olvasását a állapotban kezdi el, elolvassa részszót és
ekkor is -ban van.
Ha ekkor megint az részszó jönne (akárhányszor),
akkor megint csak -ba kerülne. Mivel az eredeti teljes szó elolvasása
után elfogadóban áll meg az automata (azaz a -ból tovább
olvasva a maradék szót
elfogadóba jutunk), a sok -t tartalmazó futásokkor is
lesz vele, azaz ezeket a szavakat is elfogadja.
Az eset úgy jön ki, hogy ha kihagyjuk az eredeti szóból az -t,
a maradék szót akkor is
a állapotból kezdjük el elolvasni, úgy meg elfogadunk.
|