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 $L=\{a^{n}b^{n}:n\geq 1\}$. Dette er generert av grammatikken $S\to aSb~|~ab$. Den er akseptert av følgende pushdownautomat $M=(\{q_{0},q_{1},q_{f}\},\{a,b\},\{a,z\},\delta ,q_{0},z,\{q_{f}\})$ hvor $\delta$ er definert som følgende

$\delta (q_{0},a,z)=(q_{0},az)$

$\delta (q_{0},a,a)=(q_{0},aa)$

$\delta (q_{0},b,a)=(q_{1},\varepsilon )$

$\delta (q_{1},b,a)=(q_{1},\varepsilon )$

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.