Svojstvo napuhavanja za kontekstno neovisne jezike

Izvor: Wikipedija
Skoči na: orijentacija, traži

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[uredi VE | uredi]

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

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

uv ixy iz je u L za svaki cijeli broj i ≥ 0.

Uporaba svojstva[uredi VE | uredi]

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

Možemo pokazati da jezik L = {ajbjcj: 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 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, uvixyiz 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 ajbjcj, 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, uv2xy2z mora također biti u L. Budući da v i y ne mogu oba biti prazna, | uv2xy2z | >
      | uvxyz |, pa smo dodali znakove.
    2. Ali 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,
      uv2xy2z 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[uredi VE | uredi]

Izvori[uredi VE | uredi]