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 $G=(N,T,P,\sigma ),$ kde N je množina neterminálnych symbolov, T je množina terminálnych symbolov, $P\subseteq N\times T^{\ast }(N\cup \{\epsilon \})$ je množina prepisovacích pravidiel a $\sigma \in N$ 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 ${\Rightarrow }_G$ na $(N\cup T{)}^{\ast }$ definovaná nasledovne:

$x{\Rightarrow }_{G}y⟺\mathrm{\exists }{w}_1,w_2\in (N\cup T{)}^{\ast }\mathrm{\exists }(u\to v)\in P:x=w_{1}u{w}_2\wedge y=w_{1}v{w}_2.$

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:

$x{\Rightarrow }_{G}y⟺\mathrm{\exists }w\in T^{\ast }\mathrm{\exists }(\xi \to v)\in P:x=w\xi \wedge y=wv.$

Jazyk akceptovaný regulárnou gramatikou sa definuje nasledovne:

$L(G)=\{w\in T^{\ast }|\sigma {\Rightarrow }^{\ast }w\}.$

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é.