Regulární gramatika

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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 X \rightarrow wY a X \rightarrow w, kde X,Y jsou neterminály a w je řetězcem terminálů. Gramatika také může obsahovat pravidlo S \rightarrow \epsilon v případě, že se S 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 X \rightarrow Yw a X \rightarrow w, 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.

Gramatika je ve standardní formě (regulární formě), jestliže obsahuje pouze pravidla tvaru X \rightarrow aY a X \rightarrow \lambda, 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.