Regulárna gramatika

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

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[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

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.