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

editovat

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

editovat

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

editovat

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

editovat

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

editovat

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

editovat

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