Kontekstno nezavisni jezik
Ovaj članak ili neki od njegovih odlomaka nije dovoljno potkrijepljen izvorima (literatura, veb-sajtovi ili drugi izvori). |
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]
- Michael Sipser - Introduction to the Theory of Computation, PWS Publishing, 1997; ISBN 0-534-94728-X