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říkladyEditovat

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é vlastnostiEditovat

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ánkyEditovat

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í formyEditovat

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í formaEditovat

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í formaEditovat

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