Redigerer Kontekstfritt språk

Et '''kontekstfritt språk''' er [[Formelt språk|språket]] generert av en [[kontekstfri grammatikk]].

Innenfor [[programmeringsspråk]] har kontekstfrie språk ei rekke anvendelser. De fleste [[Aritmetikk|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 <math>L = \{a^nb^n:n\geq1\}</math>. Dette er generert av grammatikken <math>S\to aSb ~|~ ab</math>. Den er akseptert av følgende [[pushdownautomat]] <math>M=(\{q_0,q_1,q_f\}, \{a,b\}, \{a,z\}, \delta, q_0, z, \{q_f\})</math> hvor <math>\delta</math> er definert som følgende

<math>\delta(q_0, a, z) = (q_0, az)</math>

<math>\delta(q_0, a, a) = (q_0, aa)</math>

<math>\delta(q_0, b, a) = (q_1, \varepsilon)</math>

<math>\delta(q_1, b, a) = (q_1, \varepsilon)</math>

== 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.
* [[Kleenestjerne|Kleenestjerna]] av L
* Reverseringa av L
* [[Union]]en av L og P
* [[Konkatenering|Konkateneringa]] av L og P
* Bildet under en [[homomorfisme]] (eller en invers homomorfisme)
* [[Sirkulærskifte|Det sirkulære skiftet]] av språket
Kontekstfrie språk er altså ikke lukket under [[Komplement (mengdelære)|komplement]] og [[Snitt (mengdelære)|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]]