Kontextový jazyk

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.

[editovat] Příklad

Jazyk L = { aⁿ : 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.

[editovat] Vlastnosti

• Průnik, sjednocení a zřetězení dvou kontextovch jazyků je kontextový jazyk.
• Doplňek kontextového jazyka je kontextový jazyk.
• Každý bezkontextový jazyk je kontextový.