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 rediger

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 rediger

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.

Kontekstfrie språk er altså ikke lukket under komplement og snitt.

Se også rediger

Litteratur rediger

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