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 ${\displaystyle L=\{a^{n}b^{n}:n\geq 1\}}$, jazyk všech slov sudé délky ve kterých první polovinu tvoří znaky ${\displaystyle a}$ a druhou polovinu znaky ${\displaystyle b}$. ${\displaystyle L}$ je generovaný gramatikou ${\displaystyle S\to aSb~|~ab}$ a je akceptovaný zásobníkovým automatem ${\displaystyle M=(\{q_{0},q_{1},q_{f}\},\{a,b\},\{a,z\},\delta ,q_{0},z,\{q_{f}\})}$ kde ${\displaystyle \delta }$ je definována následovně:

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 ${\displaystyle S\to SS~|~(S)~|~\lambda }$ nebo také ${\displaystyle 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 ${\displaystyle X\to YZ~|~a}$, kde ${\displaystyle X,Y,Z}$ jsou neterminály a ${\displaystyle a}$ je terminální symbol.

Greibachové normální forma

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