Kontekstno nezavisni jezik

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web-stranice ili drugi izvori).
Ako se pravilno ne potkrijepe validnim izvorima, sporne rečenice i navodi mogli bi biti obrisani. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci te nakon toga možete ukloniti ovaj šablon.

Kontekstno nezavisni jezik (rjeđe još i kontekstno slobodni jezik) je formalni jezik koji je element skupa jezika kojeg definišu kontekstno nezavisne gramatike. Skup kontekstno nezavisnih jezika je identičan skupu jezika koje prihvataju potisni automati.

Primjeri[uredi | uredi izvor]

Kanonski primjer kontekstno nezavisnog jezika jest , jezik svih nepraznih nizova znakova (simbola) parne dužine, čiju prvu polovicu čine znakovi , dok drugu polovicu čine znakovi . generiše gramatika te prihvata potisni automat gdje je funkcija prijelaza definisana na sljedeći način:





Kontekstno nezavisni jezici imaju mnoge primjene u programskim jezicima; na primjer - jezik svih pravilno uparenih zagrada generiše gramatika . Također, većinu aritmetičkih izraza mogu generisati kontekstno nezavisne gramatike.

Svojstva zatvorenosti[uredi | uredi izvor]

Kontekstno nezavisni jezici su zatvoreni nad sljedećim operacijama. To jest, ako su L i P kontekstno nezavisni jezici i D je regularni jezik, sljedeći jezici su također kontekstno nezavisni:

  • Kleeneov operator nad jezikom L
  • homeomorfizam φ(L) jezika L
  • nadovezivanje (konkatenacija) jezika L i jezika P
  • unija jezika L i jezika P
  • presjek (sa regularnim jezikom) jezika L i jezika D

Kontekstno nezavisni jezici nisu zatvoreni nad operacijama komplementa, presjeka i razlike.

Također pogledajte[uredi | uredi izvor]

Reference[uredi | uredi izvor]