ez nem a mi jegyzetünk csak rágugliztam, hátha találok valami egyszerűbb leírást hozzá
hát nem.
48. Tétel. (Bar-Hillel lemma) Bármely L környezetfüggetlen nyelvhez létezik olyan n természetes szám, hogy ∀z∈L esetén |z|>n szóra z=uvwxy alakban írható, ahol |vwx| ≤ n, vx≠λ és uviwxiy∈L 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 z∈L(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| ≤ 2k. Tegyük fel, hogy az N elemeinek száma j és legyen n=2j+1. Ha most z∈L é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 A∈N 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=vwx valamely v, x∈T* szavakra. Emellett nyilván z=ury is teljesül valamilyen u, y∈T* szavakra. Az A változó szóban forgó előfordulásainak a megválasztása miatt |r| ≤ 2j+1. Másrészt S⇒*uAy és A⇒*vAx is fennáll, tehát tetszőleges i ≥ 0 egész számra S⇒*uviwxiy. Itt nem lehet v és x mindkettő λ, mert az A⇒*vAx 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 → BC alakú szabály alkalmazása lehet, s ezért |vx| ≥ 1, miután a nyelvtanunk λ- mentes. Ezzel befejeztük a lemma bizonyítását. ∎
csak mert a mi jegyzetünk még szebb
This post was edited by Anarkin on Jan 4 2014 10:05am