Chomského hierarchie: Porovnání verzí
Smazaný obsah Přidaný obsah
m robot změnil: fa:وراثت چامسکی; kosmetické úpravy |
Bez shrnutí editace |
||
Řádek 12:
;Gramatiky typu 2 ([[Bezkontextová gramatika|bezkontextové gramatiky]])
:Generují [[bezkontextový jazyk|bezkontextové jazyky]]. Skládají se z pravidel <math>A \rightarrow \gamma</math> s neterminálem <math>A</math> a řetězcem terminálů a neterminálů <math>\gamma</math>. Pravidlo <math>S \rightarrow \epsilon</math> je povoleno, pokud se <math>S</math> nevyskytuje na pravé straně žádného pravidla. Tyto jazyky jsou právě jazyky rozpoznatelné nějakým nedeterministickým [[zásobníkový automat|zásobníkovým automatem]].
:Upřesnění: Gamatiky typu 2 mohou obsahovat <math>\epsilon</math> přechody. Přesto jsou podmnožinou gramatik typu 1, protože existuje algoritmus na převod libovolné gramatiky typu 2 na gramatiku bez <math>\epsilon</math> pravidel.
;Gramatiky typu 3 ([[Regulární gramatika|regulární gramatiky]])
| |||