# 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,a x) = (q1,x)
δ(q1,b,a x) = (q1,x)
δ(q1,b,b z) = (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ý.

## [editovat] 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):

### [editovat] Chomského normální forma

Gramatika je v chomského normální formě, pokud obsahuje pouze pravidla tvaru , kde X,Y,Z jsou neterminály a a je terminální symbol.

### [editovat] Greibachové normální forma

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

Citováno z „http://cs.wikipedia.org../../../b/e/z/Bezkontextov%C3%BD_jazyk.html“

Kategorie: Formální jazyky

##### Views

- Článek
- Diskuse
- Aktuální verze

##### Hledání

##### V jiných jazycích

- Bosanski
- Deutsch
- English
- Suomi
- עברית
- Hrvatski
- Italiano
- Polski
- Română