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