Kontekstfritt språk

Fra Wikipedia, den frie encyklopedi
Hopp til navigering Hopp til sø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[rediger | rediger kilde]

Et eksempel er følgende språk . Dette er generert av grammatikken . Den er akseptert av følgende pushdownautomat hvor er definert som følgende

Egenskaper[rediger | rediger kilde]

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.

Kontekstfrie språk er altså ikke lukket under komplement og snitt.

Se også[rediger | rediger kilde]

Litteratur[rediger | rediger kilde]

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