Kontekstno nezavisni jezik
Sa Wikipedije, slobodne enciklopedije
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.
[uredi] Primjeri
Kanonski primjer kontekstno nezavisnog jezika jest , jezik svih nepraznih nizova znakova (simbola) parne dužine, čiju prvu polovicu čine znakovi a, dok drugu polovicu čine znakovi b. L generiše gramatika
te prihvata potisni automat M = ({q0,q1,qf},{a},{a,b,z},δ,q0,{qf}) gdje je funkcija prijelaza δ definisana na sljedeći način:
δ(q0,a,z) = (q0,a)
δ(q0,b,ax) = (q1,x)
δ(q1,b,ax) = (q1,x)
δ(q1,b,bz) = (qf,z)
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.
[uredi] Svojstva zatvorenosti
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 L * 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.
[uredi] Reference
- Michael Sipser - Introduction to the Theory of Computation, PWS Publishing, 1997; ISBN 0-534-94728-X