Regulární gramatika

Regulární gramatika je typ formální gramatiky. Přesněji je to gramatika typu 3 podle Chomského hierarchie, tedy ta nejzákladnější.

Regulární gramatika se formálně zapisuje, jako čtveřice $G=(N,T,P,S)$, kde G značí regulární gramatiku, N je konečná neprázdná množina neterminálů, T je konečná neprázdná množina terminálů, P je konečná neprázdná množina nezkracujících pravidel a S je startovací neterminál z množiny N.

Regulární gramatika se využívá pro generování formálních jazyků, této vlastnosti se využívá především v oboru informatiky, pro teorii jazyků a překladačů, konečný automat založený na RG se využívá například v lexikální analýze překladače.

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.^[zdroj⁠?!] Rozšíření regulární gramatiky o řetězce vytvořené z terminálů na levé straně a neterminálů na pravé, se nazývá pravá regulární gramatika.

Obdobně se definují i levé regulá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 ekvivalentní, například právě pomocí derivačních stromů.

Gramatika je ve standardní Chomského formě CNF (regulární formě), jestliže obsahuje pouze pravidla tvaru $A\rightarrow BC$ a $B\rightarrow a$, kde A,B a C jsou neterminály, a je právě jeden terminál.

Jazyky generované regulárními gramatikami, jsou nazývány regulární jazyky a jsou to takové jazyky, které přijímá konečným automatem.

To zda je gramatika opravdu regulární, nebo spíše, že není, se dá dokázat pomocí důkazu sporem za použití Pumping Lemma.