Svojstvo napuhavanja za kontekstno neovisne jezike

Također poznata i kao Bar-Hillelelova lema. Svojstvo napuhavanja za kontekstno neovisne jezike je lema koja izražava svojstvo koje svi kontekstno neovisni jezici moraju zadovoljavati. Primarna uporaba leme jest prilikom dokazivanja da jezik nije kontekstno neovisan.

Svojstvo napuhavanja za kontekstno neovisne jezike se ne može koristiti prilikom dokazivanja da proizvoljan ne-kontekstno neovisni jezik nije kontekstno neovisan. U nekim slučajevima se mora koristiti općenitija Ogdenova lema.

Formalni iskaz

Ako je jezik L kontekstno neovisan, tada postoji cijeli broj p > 0 takav da svaki niz znakova w u L za koji je |w| ≥ p (gdje je p duljina napuhavanja) može biti zapisan kao

w = uvxyz

s podnizovima u, v, x, y i z, takvim da |vxy| ≤ p, |vy| ≥ 1, i

uv ⁱxy ⁱz je u L za svaki cijeli broj i ≥ 0.

Uporaba svojstva

Svojstvo napuhavanja za kontekstno neovisne jezike se može koristiti prilikom pokazivanja da neki jezici nisu kontekstno neovisni.

Možemo pokazati da jezik L = {a^jb^jc^j: j>0} nije kontekstno neovisan.

1. Pretpostavimo da je L kontekstno neovisan.
   1. Uvjeti:
      1. | vxy | ≤ p. To jest, srednji dio nije predug.
      2. vy ≠ ε (prazan). S obzirom na to da su v i y dijelovi koje "napuhavamo", ovaj uvjet kaže da barem jedan od nizova znakova koje napuhavamo mora biti neprazan.
      3. Za sve i ≥ 0, uvⁱxyⁱz je u L. To jest, nizovi znakova v i y mogu biti "napuhani" bilo koji broj puta, uključujući 0, i rezultirajući niz znakova će još uvijek biti element jezika L.
2. Ako je niz znakova w ∈ L pri čemu je | w | > p, slijedi w = uvxyz, pri čemu je | vxy | ≤ p
3. Sada, odaberimo vrijednost za i koja je veća od p.
4. Potom, kadgod se vxy pojavi u nizu znakova a^jb^jc^j, vxy ne može sadržavati više od dva različita znaka, pošto je krajnje desno a j+1 pozicija udaljeno od krajnjeg desnog c.
   1. Npr: Mogu biti svi znakovi a, svi znakovi b, ili svi znakovi c, ili mogu biti znakovi a i znakovi b, ili mogu biti znakovi b i znakovi c.
      1. Slijedi da niz znakova vxy ne može sadržavati više od dva različita znaka, ali po svojstvu napuhavanja također ne može biti prazan, te stoga mora sadržavati barem jedan znak.
5. Sada možemo započeti "napuhavanje".
   1. Budući da je uvxyz u L, uv²xy²z mora također biti u L. Budući da v i y ne mogu oba biti prazna, | uv²xy²z | >
      | uvxyz |, pa smo dodali znakove.
   2. Budući da vy ne sadrži sva tri različita znaka, nismo mogli dodati isti broj svih znakova. Napuhali smo više znakova i tako protuslovili izvornu definiciju jezika L. Stoga,
      uv²xy²z ne može biti u L.
6. Došli smo do protuslovlja (kontradikcije). Stoga je naša izvorna pretpostavka, da je jezik L kontekstno neovisan, pogrešna. 

Vidjeti također

• Svojstvo napuhavanja za regularne jezike
• Formalni jezik
• Ogdenova lema

Izvori

• Michael Sipser. 1997. Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X
• Siniša Srbljić. 2003. Jezični procesori 1. Element. ISBN 953-197-129-3