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 , jazyk všech slov sudé délky ve kterých první polovinu tvoří znaky a druhou polovinu znaky . je generovaný gramatikou a je akceptovaný zásobníkovým automatem kde 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 nebo také

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 , kde jsou neterminály a je terminální symbol.

Greibachové normální forma

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