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).
[editovat] 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 a druhou polovinu znaky b. L je generovaný gramatikou 
a je akceptovaný zásobníkovým automatem M = ({q0,q1,qf},{a},{a,b,z},δ,q0,{qf}) kde δ je definována následovně:
δ(q0,a,z) = (q0,a)
δ(q0,b,ax) = (q1,x)
δ(q1,b,ax) = (q1,x)
δ(q1,b,bz) = (qf,z)
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é 
[editovat] Uzávěrové vlastnosti
Bezkontextové jazyky jsou uzavřeny na zřetězení, sjednocení a rozdíl s regulárním jazykem, ale ne na průnik a rozdíl.
[editovat] Podívejte se též na
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ý.
