Bezkontextový jazyk
Author
Albert FloresBezkontextový 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 L = \{a^nb^n:n\geq1\}, jazyk všech slov sudé délky ve kterých první polovinu tvoří znaky a a druhou polovinu znaky b. L je generovaný gramatikou S\to aSb ~|~ ab a je akceptovaný zásobníkovým automatem M=(\{q_0,q_1,q_f\}, \{a,b\}, \{a,z\}, \delta, q_0, z, \{q_f\}) kde \delta je definována následovně:
\delta(q_0, a, z) = (q_0, az)
\delta(q_0, a, a) = (q_0, aa)
\delta(q_0, b, a) = (q_1, \varepsilon)
\delta(q_1, b, a) = (q_1, \varepsilon)
Bezkontextové jazyky jsou využívány především v programovacích jazycích. Například dobře uzávorkovaný výraz (tj. +more výraz, kde počet '(' je stejný jako počet ')') je generován gramatikou S\to SS ~|~ (S) ~|~ \lambda nebo také S\to S(S) ~|~ \lambda.
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 X \to YZ ~|~ a , kde X, Y, Z jsou neterminály a a je terminální symbol.
Greibachové normální forma
Gramatika je v greibachové normální formě, pokud obsahuje pouze pravidla tvaru X \to a\alpha , kde \alpha obsahuje libovolný (i nulový) počet neterminálů.