Regulárna gramatika

Regulárna gramatika je v teórii formálnych jazykov bezkontextová gramatika taká, že pravá strana každého prepisovacieho pravidla obsahuje najviac jeden neterminálny symbol, ktorý navyše musí byť na konci pravej strany pravidla.

Definícia 

Formálne sa regulárna gramatika definuje ako štvorica  kde N je množina neterminálnych symbolov, T je množina terminálnych symbolov,  je množina prepisovacích pravidiel a  je počiatočný neterminál.

Krok odvodenia a jazyk akceptovaný regulárnou gramatikou sa definujú rovnako, ako pri bezkontextových gramatikách alebo frázových gramatikách. Krok odvodenia je binárna relácia  na  definovaná nasledovne:

 

Keďže má regulárna gramatika oproti frázovým gramatikám obmedzený tvar prepisovacích pravidiel, je možné predchádzajúcu definíciu prepísať ako:

 

Jazyk akceptovaný regulárnou gramatikou sa definuje nasledovne:

Sila 

Jazyk, pre ktorý existuje regulárna gramatika, ktorá ho generuje, sa nazýva regulárny jazyk. Trieda jazykov generovaných regulárnymi gramatikami (teda trieda regulárnych jazykov) sa rovná triede jazykov akceptovaných konečnými automatmi. Regulárne gramatiky a konečné automaty sú teda z hľadiska popisnej sily ekvivalentné.

Formálne jazyky