Otvoriť hlavné menu

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íciaUpraviť

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:

 

SilaUpraviť

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, automaty a gramatiky
Chomského
hierarchia
Gramatiky Jazyky Minimálny
automat
Typ-0 Frázová Rekurzívne vyčísliteľný Turingov stroj
Rekurzívny Vždy zastavujúci Turingov stroj
Typ-1 Kontextová Kontextový (Nedeterministický) lineárne ohraničený
Typ-2 Bezkontextová Bezkontextový (Nedeterministický) zásobníkový
Typ-3 Regulárna Regulárny Konečný
Každá množina jazykov alebo gramatík je vlastnou nadmnožinou množiny priamo pod ňou.