Regulární gramatika

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ů. Regulární gramatiky se také nazývají pravé lineární gramatiky.

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.

Regulární gramatika je ve standardní 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.

Kategorie: Formální jazyky

Regulární gramatika v jiných jazycích: Deutsch, English, Español, Français, Hrvatski, Italiano, 日本語, 한국어, Nederlands, Polski, Português, Русский, 中文

Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „http://cs.wikipedia.org/wiki/Regul%C3%A1rn%C3%AD_gramatika“
Stránka byla naposledy upravena v Stránka byla naposledy editována 23. 12. 2007 v 06:37.
Veškerý text je dostupný za podmínek GNU Free Documentation License (Autorské právo pro podrobnosti).