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 $L=\{a^{n}b^{n}:n\geq 1\}$. Dette språket er generert av grammatikken $S\to aSb~|~ab$. Det er akseptert av einpushdownautomat definert ved$M=(\{q_{0},q_{1},q_{f}\},\{a,b\},\{a,z\},\delta ,q_{0},z,\{q_{f}\})$ der $\delta$ er definert som:

$\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 )$

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.