Regulární gramatika
Z Wikipedie, otevřené encyklopedie
Regulární gramatika je typ formální gramatiky. Přesněji je to gramatika typu 3 podle Chomského hierarchie.
Gramatika typu 3 obsahuje pravidla tvaru 
a 
, kde X,Y jsou neterminály a w je řetězcem terminálů. Regulární gramatiky se také nazývají pravé lineární gramatiky.
Obdobně se definují i levé lineární gramatiky, které obsahují pravidla tvaru 
a , kde X,Y jsou neterminály a w je řetězcem terminálů. Lze dokázat, že pravé a levé lineární gramatiky jsou ekvivalentni.
Regulární gramatika je ve standardní formě, jestliže obsahuje pouze pravidla tvaru 
a 
, kde X,Y jsou neterminály, a je právě jeden terminál.
Jazyky generované regulárními gramatikami jsou právě jazyky rozpoznatelné konečným automatem.
