Kontekstfritt språk

Frå Wikipedia – det frie oppslagsverket
Hopp til navigering Hopp til sø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[endre | endre wikiteksten]

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[endre | endre wikiteksten]

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[endre | endre wikiteksten]

Litteratur[endre | endre wikiteksten]

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