5 Kontextové jazyky
Formální jazyk je kontextový právě tehdy, když jej lze generovat kontextovou gramatikou. Pro kontextové jazyky dále platí, že je lze:
- přijmout nedeterministickým lineárně omezeným Turingovým strojem,
- generovat nezkracující gramatikou.
Tato třída jazyků je uzavřená pro všechny námi definované operace (sjednocení, průnik, rozdíl, doplněk, zřetězení, iterace).