From Wikipedia, the free encyclopedia
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.
Ovaj članak ili neki od njegovih odlomaka nije dovoljno potkrijepljen izvorima (literatura, veb-sajtovi ili drugi izvori). |
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.
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:
Kontekstno nezavisni jezici nisu zatvoreni nad operacijama komplementa, presjeka i razlike.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.