Regulární gramatika: Porovnání verzí
Smazaný obsah Přidaný obsah
m překlep |
Bez shrnutí editace značka: editace z Vizuálního editoru |
||
Řá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>S \rightarrow \epsilon</math> v případě, že se <math>S</math> nevyskytuje na pravé straně žádného pravidla.{{Fakt/dne|20150202020202|tady je ta podminka nezajimava}} Rozšíření regulární gramatiky o řetězce se nazývá '''pravá
Obdobně se definují i '''levé
Lze dokázat, že pravé a levé lineární gramatiky jsou ekvivalentní.
|