Bezkontextový jazyk

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=\{a^{n}b^{n}:n\geq 1\}$ , 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\to aSb~|~ab$ a je akceptovaný zásobníkovým automatem $M=(\{q_{0},q_{1},q_{f}\},\{a,b\},\{a,z\},\delta ,q_{0},z,\{q_{f}\})$ kde $\delta$ je definována následovně:

$\delta (q_{0},a,z)=(q_{0},az)$
$\delta (q_{0},a,a)=(q_{0},aa)$
$\delta (q_{0},b,a)=(q_{1},\varepsilon )$
$\delta (q_{1},b,a)=(q_{1},\varepsilon )$

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\to SS~|~(S)~|~\lambda$ nebo také $S\to S(S)~|~\lambda$

Uzávěrové vlastnosti

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

Související články

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ý.

Normální formy

Každý bezkontextový jazyk lze převést do obou z následujících normálních forem (někdy také normálního tvaru):

Chomského normální forma

Gramatika je v chomského normální formě, pokud obsahuje pouze pravidla tvaru $X\to YZ~|~a$ , kde $X,Y,Z$ jsou neterminály a $a$ je terminální symbol.

Greibachové normální forma

Gramatika je v greibachové normální formě, pokud obsahuje pouze pravidla tvaru $X\to a\alpha$ , kde $\alpha$ obsahuje libovolný (i nulový) počet neterminálů.