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 L = \{a^nb^n:n\geq1\}, 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 S\to aSb ~|~ ab 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 S\to SS ~|~ (S) ~|~ \lambda. 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) L \circ P jezika L i jezika P
  • unija L \cup P jezika L i jezika P
  • presjek (sa regularnim jezikom) L \cap D 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