7.4. A Bar-Hillel lemma

A környezetfüggetlen nyelvek esetén a levezetések fa ábrázolása (a levezetési fa) segítségével fogjuk belátni a következő iterációs lemmát:

48. Tétel. (Bar-Hillel lemma) Bármely L környezetfüggetlen nyelvhez létezik olyan n természetes szám, hogy ∀zL esetén |z|>n szóra z=u v w x y alakban írható, ahol |v w x| ≤ n, v xλ és u v i w x i yL minden i ≥ 0 egész számra.

Bizonyítás. Röviden ez a lemma azt mondja ki, hogy a nyelvben minden elég hosszú szóhoz végtelen sok rokon szerkezetű további szó található. A bizonyításnál elég λ- mentes nyelvtanra szorítkoznunk. Feltételezzük továbbá, hogy a nyelvtanunk Chomsky-féle normálalakban adott. Ha egy zL(G) szónak a levezetése olyan fával ábrázolható, amelyben a leghosszabb út k hosszúságú, akkor a Chomsky-féle normálalak miatt |z| ≤ 2 k . Tegyük fel, hogy az N elemeinek száma j és legyen n=2 j+1. Ha most zL és |z|>n, akkor az S* z levezetési fájában a leghosszabb útnak j- nél hosszabbnak kell lennie. Vegyük ennek az útnak az utolsó j+1 hosszúságú szakaszát. Lesz olyan AN változó, amely ezen a szakaszon legalább kétszer előfordul.

Vegyük ennek a változónak két ilyen előfordulását. Ezek közül az elsőhöz (az S- hez közelebb fekvőhöz) tartozó részfa végpontjainak megfelelő szó legyen r, a másik részfa végpontjainak megfelelő szó legyen w. Ezekre nyilván A* r és A* w, továbbá a w részszava r- nek, tehát r=v w x valamely v, xT * szavakra. Emellett nyilván z=u r y is teljesül valamilyen u, yT * szavakra. Az A változó szóban forgó előfordulásainak a megválasztása miatt |r| ≤ 2 j+1. Másrészt S* u A y és A* v A x is fennáll, tehát tetszőleges i ≥ 0 egész számra S* u v i w x i y. Itt nem lehet v és x mindkettő λ, mert az A* v A x levezetés legalább egy lépést tartalmaz, tekintve, hogy az A- nak két különböző előfordulásáról van szó. Akkor pedig ebben a levezetésben az első lépés csak egy A → B C alakú szabály alkalmazása lehet, s ezért |v x| ≥ 1, miután a nyelvtanunk λ- mentes. Ezzel befejeztük a lemma bizonyítását. ∎

7.9. példa - A Bar-Hillel lemma alkalmazása

Az {a j b j c j |j ≥ 1} nyelv nem környezetfüggetlen.


Ha volna olyan környezetfüggetlen nyelvtan, amely generálja ezt a nyelvet, akkor a lemma szerint volna olyan z=u v w x y szó, hogy v xλ, és minden i ≥ 0- ra u v i w x i y ehhez a nyelvhez tartozik. Az u v i w x i y=a j b j c j összefüggést azonban az u, v, w, x, y szavak semmilyen konkrét választása mellett sem lehet végtelen sok i- re és j- re kielégíteni. Ugyanis v és x közül egyik sem tartalmazhat többféle betűt (hiszen ekkor a pumpálás során létrejövő szó alakja nem a * b * c * lenne). Ha viszont csak egyfélét tartalmaznak, akkor az a, b, c közül legalább az egyiknek a kitevője i- től független lesz. ★

A lemma alapján azt is kijelenthetjük, hogy ha egy környezetfüggetlen nyelv végtelen, akkor igaz rá a konstansnövekmény elve, vagyis van olyan konstans n∈ℕ, hogy minden u szavához van a nyelvnek olyan szava, melynek hossza nem több, mint |u|+n.

További példákat mutatunk a lemma alkalmazására:

7.10. példa - Bar-Hillel lemma 1. feladat


Bizonyítsa be, hogy az L ={aibjcidj
               
i,j ≥ 1} nyelv nem környezetfüggetlen.
 


Megoldás:
Tegyük fel indirekt, hogy megadható olyan n természetes szám, amely a Bar-Hillel lemma szerint
minden környezetfüggetlen nyelv esetében létezik!
Tekintsük az a
               2n
               

               b
               2n
               

               c
               2n
               

               d
               2n
               
 szót, ami nyilvánvalóan eleme a nyelvnek és hosszabb n -nél.

Legyen a
               2n
               

               b
               2n
               

               c
               2n
               

               d
               2n
               

                = uvwxy, ahol vx ≠ λ, ekkor uv
               2
               wx
               2
               y ∈ L.

Ha v és x közül valamelyik tartalmaz a-t, akkor |vwx| ≤ n miatt egyikük sem tartalmazhat c-t.
Így a pumpálás kivezet a nyelvből.  

Ha viszont v és x közül valamelyik tartalmaz b-t, akkor |vwx| ≤ n miatt egyikük sem tartalmazhat d-t;
a pumpálás így is kivezet a nyelvből.

Így tehát sem v, sem x nem tartalmazhat sem a-t, sem b-t, akkor viszont a szó hossza nem változhat,
ami ellentmond a lemma állításának. ★


7.11. példa - Bar-Hillel lemma 2. feladat


Bizonyítsa be, hogy a L={wcw | w ∈ {a,b}
                  *
               
} nyelv nem környezetfüggetlen.


Megoldás:
Tegyük fel indirekt, hogy L környezetfüggetlen, ekkor legyen n a lemma által adott konstans.
Tekintsük az a
               2n
               

               b
               2n
               

               ca
               2n
               

               b
               2n
               
 szót. Ekkor vx ≠ λ miatt a v az első
a
               2n
               

               b
               2n
               
 blokk részszava kell, hogy legyen, amíg az x a c utáni blokk részszava.
 
Ellenkező esetben vagy a c-k száma változna a pumpálás során, vagy a c előtti, illetve utáni
blokkok hossza változna különbözőre.

vwx | ≤ n miatt viszont így a v csak b-ket, az x pedig csak a-kat tartalmazhat, így viszont
az iteráció kivezet a nyelvből. ★


7.12. példa - Bar-Hillel lemma 3. feladat



Bizonyítsa be, hogy az L={a
               
                  k
                  2
               
k ≥ 1} nyelv nem környezetfüggetlen!
Megoldás:
Tegyük fel indirekt, hogy L környezetfüggetlen!
Ekkor igaz rá a Bar-Hillel lemma, tehát létezik olyan n szám,
hogy minden n-től hosszabb L-beli szó felírható a lemma szerinti uvwxy alakban,
hogy uvvwxxy, uvvvwxxxy ... is L-beli.
Legyen m
               2 > n és a
               
                  m
                  2
               
=uvwxy és |vx| = c > 0!
Ekkor m
               2+c,m
               2+2c,m
               2+3c... is négyzetszám kell legyen.
Kérdés tehát, hogy van-e olyan szigorúan monoton növekvő számtani sorozat,
melynek minden eleme négyzetszám?
Mivel két szomszédos négyzetszám különbsége minden határon túl nő,
ezért egyszer meghaladja c-t is, tehát nincs.
Vagyis ellentmondásra jutottunk. Az ellentmondás oka csak az indirekt feltétel hamis volta lehet. ★


7.13. példa - Bar-Hillel lemma 4. feladat


Környezetfüggetlen-e az L={0
                  m
               
12m
               
}| m ≥ 1} nyelv?
Ha igen, adjon meg hozzá környezetfüggetlen grammatikát,ha nem, bizonyítsa be!


Megoldás:
Ha a v csak 1-eseket, az x csak kétszer annyi 0-t tartalmaz, akkor azok hatványozásával
továbbra is L-beli szavakat kapunk, ezért a Bar- Hillel lemmával nem jutunk ellentmondásra.
pl:
v=0,
w=λ,
x=11.
Ekkor a lemma szerinti állandó n = 3.
A nyelv tehát lehet környezetfüggetlen, és meg is tudunk adni egy, a nyelvet generáló nyelvtant:
G=({S},{0, 1}, S, {S → 0S11, S → 011}). ★


7.14. példa - Bar-Hillel lemma 5. feladat


Környezetfüggetlen-e az L={0
                  i
               
12i
               
0
                  j
               
i,j ≥ 1} nyelv?
Ha igen, adjon meg hozzá környezetfüggetlen grammatikát, ha nem, bizonyítsa be!


Megoldás:
Két alapjában eltérő módon is kielégíthető a Bar-Hillel lemma:
v-t 0
                  i
               
-ből, x-et 12i
               
-ből választjuk, úgy, hogy x kétszer hosszabb.
 Pl:
 v=0,
 w=λ,
 x=11.
Ekkor n=3.
v-t és x-et is 0
                  j
               
-ből válaszjuk.
 Pl:
 v=0,
 w=λ,
 x=λ.
Ekkor n=3.
G=({S, A, B},{0, 1}, S,{S → AB, A → 0A11, A  → 011, B → 0, B → 0B}) pedig egy grammatika,
amely a keresett nyelvet állítja elő. ★
 


7.15. példa - Bar-Hillel lemma 6. feladat

Környezetfüggetlen-e az L={0 i 1 j 02i |i,j  ≥ 1} nyelv?

Megoldás:
Ha a két szélén választjuk ki a "pumpálandó" részeket, akkor ezek távolsága bármekkorára nőhet,
így nem tudjuk n alatt tartani, ezért a két "pumpálandó" részt válasszuk az 1-esek közül, illetve
az egyik legyen λ:
v=1,
w=λ,
x=λ,
n=3.
Vagyis a Bar-Hillel lemmával nem kerültünk ellentmondásba, és ez a nyelv egyébként
tényleg környezetfüggetlen:
G=({S, A}, {0, 1}, S, {S → 0S00, S → 0A00, A → 1A, A → 1})
2-es típusú grammatika pontosan ezt a nyelvet generálja.
Először a 0-kat állítjuk elő S → 0S00 szabály i-1 szeri alkalmazásával,
majd a szó közepét töltjük fel 1-esekkel. ★
 


7.16. példa - Bar-Hillel lemma 7. feladat



               L={api
                  

               
|pi
               
 az i-edik prím i ≥ 1}
Bizonyítsa be, hogy az L nyelv nem környezetfüggetlen!
 


Megoldás:
Tegyük fel, hogy L környezetfüggetlen! Ekkor alkalmazható rá a Bar-Hillel lemma,
vagyis, ha c olyan prím, hogy nagyobb a lemma által létező n-nél, és az vx hossza m,
akkor c+mc+2m, ..., c+cm is prím.
Márpedig c+cm=c(1+m) nem lehet prím. Vagyis ellentmondásra jutottunk. ★
 


7.17. példa - Bar-Hillel lemma 8. feladat


Legyen L={pp
               -1|p
               -1 a p tükörképe, p ∈ T}, ahol T tetszőleges ábécé.
Környezetfüggetlen-e az L nyelv?
 


Megoldás:
Tetszőleges L-beli szó esetén, ha a Bar-Hillel lemma szerinti v és x részszavakat
szimmetrikusan választjuk, akkor ezek "pumpálásával" továbbra is L-beli szavakat kapunk,
tehát az L nyelv "kiállja" a Bar-Hillel lemmát.
Hogy valóban környezetfüggetlen, ahhoz csak azt kell látni, hogy
ha a grammatikának csak S → aSa (a ∈ T) és S → λ típusú
szabályai vannak, akkor az pontosan az L nyelvet állítja elő. ★
 


7.18. példa - Bar-Hillel lemma 9. feladat



               L={ax
               
|x=m
               2+3m+1, m ≥ 1}
Bizonyítsa be, hogy az L nyelv nem környezetfüggetlen!


Megoldás:
A bizonyítás azon múlik, hogy két szomszédos ilyen alakú szám távolsága
[(m+1)2+3(m+1)+1]-[m
               2+3m+1]=2m+4
minden határon túl nőhet, az uvwxy, uvvwxxy, uvvvwxxxy ... hosszai pedig számtani
sorozatot alkotnak. ★