Kontextový jazyk

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Kontextový jazyk je formální jazyk, který je vygenerovatelný nějakou kontextovou gramatikou. Je to jeden ze čtyř typů jazyků Chomského hierarchie, v praxi se využívá jen zřídka.

Příklad[editovat | editovat zdroj]

Jazyk L = { an : n je prvočíslo } není bezkontextový, ale je kontextový. Lze to ukázat třeba tak, že sestrojíme lineárně ohraničený Turingův stroj, který bude L rozpoznávat.

Vlastnosti[editovat | editovat zdroj]

  • Průnik, sjednocení a zřetězení dvou kontextových jazyků je kontextový jazyk.
  • Doplněk kontextového jazyka je kontextový jazyk.
  • Každý bezkontextový jazyk je kontextový.