Regulární gramatika: Porovnání verzí

Smazaný obsah Přidaný obsah
FIXME: možná oprava - symbol S nebyl definován, předpokládám, že je tím myšlen neterminální symbol, který byl zaveden jako X či Y (proto taková oprava)
Verze 7265766 uživatele 84.16.123.194 (diskuse) zrušena --- omyl
Řádek 1:
'''Regulární gramatika''' je typ [[Formální gramatika|formální gramatiky]]. Přesněji je to gramatika typu 3 podle [[Chomského hierarchie]].
 
Gramatika typu 3 obsahuje pravidla tvaru <math>X \rightarrow wY</math> a <math>X \rightarrow w</math>, kde X,Y jsou neterminály a w je řetězcem terminálů. Gramatika také může obsahovat pravidlo <math>XS \rightarrow \epsilon</math> v případě, že se <math>S</math> nevyskytuje na pravé straně žádného pravidla. Rozšíření regulární gramatiky o řetězce se nazývá '''pravá lineární gramatika'''.
 
Obdobně se definují i '''levé lineární gramatiky''', které obsahují pravidla tvaru <math>X \rightarrow Yw</math> a <math>X \rightarrow w</math>, kde X,Y jsou neterminály a w je řetězcem terminálů.