Kontekstfritt språk

Et kontekstfritt språk er språket generert av en kontekstfri grammatikk.

Innenfor programmeringsspråk har kontekstfrie språk ei rekke anvendelser. De fleste aritmetiske uttrykk er generert av kontekstfrie grammatikker. Innenfor kompilatorteknikk er teorien om kontekstfrie språk også viktig.

I Chomskyhierarkiet er kontekstfrie språk omtalt som de som genererer en type 2 grammatikk.

 Eksempel 
Et eksempel er følgende språk . Dette er generert av grammatikken . Den er akseptert av følgende pushdownautomat  hvor  er definert som følgende

 Egenskaper 
Kontekstfrie språk er lukket under følgende operasjoner. Det vil altså si at for to kontekstfrie språk L og P, så vil resultatet av operasjonen fortsatt være et kontekstfritt språk.
 Kleenestjerna av L
 Reverseringa av L
 Unionen av L og P
 Konkateneringa av L og P
 Bildet under en homomorfisme (eller en invers homomorfisme)
 Det sirkulære skiftet av språket
Kontekstfrie språk er altså ikke lukket under komplement og snitt.

 Se også 
 Chomsky normalform
 Pushdownautomat
 Pumpelemmaet for kontekstfrie språk

 Litteratur 
 Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
 Kozen, D.C. (1997), Automata and Computability, Springer.

Kategori:Formelle språk