Kontekstfritt språk

Eit kontekstfritt språk er språket generert av ein kontekstfri grammatikk.

Innanføre programmeringsspråk har kontekstfrie språk ei rekkje bruksområde. Dei fleste aritmetiske uttrykk er genererte av kontekstfrie grammatikkar. Innanføre kompilatorteknikk er teorien om kontekstfrie språk òg viktig.

I chomskyhierarkiet er kontekstfrie språk omtalt som dei formelle språka som genererer ein type 2 grammatikk.

 Døme 
Eit døme er språket . Dette språket er generert av grammatikken . Det er akseptert av einpushdownautomat definert ved der  er definert som:

 Eigenskapar 
Kontekstfrie språk er lukka under følgjande operasjonar. Det vil altså seia at for to kontekstfrie språk L og P, så vil resultatet av operasjonen framleis vera eit kontekstfritt språk.

 Kleenestjerna av L
 Reverseringa av L
 Unionen av L og P
 Konkateneringa av L og P
 Biletet under ein homomorfisme (eller ein invers homomorfisme)
 Det sirkulæret skifta av språket

Kontekstfrie språk er altså ikkje lukka under komplement og snitt.

 Sjå òg 

 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