Přeskočit na obsah

Bezkontextový jazyk

Z Wikipedie, otevřené encyklopedie

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 | editovat zdroj]

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 | editovat zdroj]

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 | editovat zdroj]

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 | editovat zdroj]

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 | editovat zdroj]

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 | editovat zdroj]

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