Bezkontextový jazyk je formální jazyk, který je akceptovaný nějakým zásobníkovým automatem. Bezkontextové jazyky mohou být vygenerovány bezkontextovými gramatikami (viz Chomského hierarchie).

Příklady

---

Typickým příkladem bezkontextového jazyka je $L\; =\; \backslash \{a^nb^n:n\backslash geq1\backslash \}$, jazyk všech slov sudé délky ve kterých první polovinu tvoří znaky $a$ a druhou polovinu znaky $b$. $L$ je generovaný gramatikou $S\backslash to\; aSb\; ~|~\; ab$ a je akceptovaný zásobníkovým automatem $M=(\backslash \{q\_0,q\_1,q\_f\backslash \},\; \backslash \{a\backslash \},\; \backslash \{a,b,z\backslash \},\; \backslash delta,\; q\_0,\; \backslash \{q\_f\backslash \})$ kde $\backslash delta$ je definována následovně:

$\backslash delta(q\_0,\; a,\; z)\; =\; (q\_0,\; a)$
$\backslash delta(q\_0,\; b,\; ax)\; =\; (q\_1,\; x)$
$\backslash delta(q\_1,\; b,\; ax)\; =\; (q\_1,\; x)$
$\backslash delta(q\_1,\; b,\; bz)\; =\; (q\_f,\; z)$

Bezkontextové jazyky jsou využívány především v programovacích jazycích. Například dobře uzávorkovaný výraz (tj. výraz, kde počet '(' je stejný jako počet ')') je generován gramatikou $S\backslash to\; SS\; ~|~\; (S)\; ~|~\; \backslash lambda$ nebo také $S\backslash to\; S(S)\; ~|~\; \backslash lambda$

Uzávěrové vlastnosti

---

Bezkontextové jazyky jsou uzavřeny na zřetězení, sjednocení a rozdíl s regulárním jazykem, ale ne na průnik a rozdíl.

Podívejte se též na

---

Pro bezkontextové jazyky existuje lemma o vkládání (pumping lemma) které udává nezbytnou podmínku, kterou musí jazyk splňovat, aby byl bezkontextový.

Formální jazyky

Kontextfreie Sprache | Context-free language | Yhteydetön kieli | שפה חופשית הקשר | Linguaggio context-free | Język bezkontekstowy | Limbaje independente de context