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

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ů.

Kategorie:Formální jazyky