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 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 \{\varepsilon\}) 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 \iff \exists w_1, w_2  \in (N \cup T)^{\ast} \exists (u \to v) \in P: x = w_1 u w_2\ \land\ 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 \iff \exists w \in T^{\ast} \exists (\xi \to v) \in P: x = w\xi\ \land\ y = wv.

Jazyk akceptovaný regulárnou gramatikou sa definuje nasledovne:

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

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.