Formální gramatika

Formální gramatika v informatice označuje strukturu, která popisuje formální jazyk. Pojmenování je zvoleno kvůli podobnosti s gramatikami používanými v přirozených jazycích.

Gramatika se skládá z množiny pravidel, pomocí kterých může být každé slovo předepsaným způsobem vygenerováno z předem daného počátečního symbolu. Generování probíhá tak, že vezmeme počáteční symbol, na něj aplikujeme kterékoli z pravidel, na získaný řetězec opět aplikujeme kterékoli z pravidel atd., dokud nevygenerujeme požadované slovo. Pokud je pro každé slovo nejvýše jeden postup generování, gramatika je jednoznačná.

Mějme například abecedu obsahující symboly ' $a$ ' a ' $b$ ', počáteční symbol je ' $S$ ' a pravidla jsou definována takto:

1.

S\longrightarrow aSb

2.

S\longrightarrow ba

začneme symbolem „ $S$ “ a vybereme pravidlo, které budeme aplikovat. Pokud vybereme 1, nahradíme ' $S$ ' řetězcem ' $aSb$ ' a obdržíme tak „ $aSb$ “. Znovuzvolením 1. pravidla nahradíme ' $S$ ' opět řetězcem ' $aSb$ ' a obdržíme „ $aaSbb$ “. Tento proces můžeme opakovat, dokud nejsou všechny symboly našeho slova z abecedy (tj. ' $a$ ' a ' $b$ '). Abychom tedy vygenerovali slovo, musíme zvolit 2. pravidlo a přepsat ' $S$ ' na ' $ba$ '. Tím obdržíme „ $aababb$ “ a jsme hotovi. Jazykem gramatiky jsou všechna slova, která dokážeme vygenerovat: $\left\{ba,abab,aababb,aaababbb,...\right\}$

Znaky z abecedy (v našem případě ' $a$ ' a ' $b$ ') se nazývají terminály, ostatní znaky ( $S$ ) se nazývají neterminály.

Formální definice

Gramatika G je čtveřice $(N,\Sigma ,P,S)$ , kde:

$N$ je konečná množina neterminálních symbolů (neterminálů).
$\Sigma$ je konečná množina terminálních symbolů disjunktní od $N$ . (Obvykle se značí řeckým písmenkem sigma.)
$P$ je konečná množina přepisovacích pravidel. Každé pravidlo je tvaru
$(\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\longrightarrow (\Sigma \cup N)^{*}$
$S$ je prvek z $N$ nazývaný počáteční symbol.

Konvence

jednotlivé terminály značíme – a, b, c, …
řetězce terminálů značíme – u, v, w, …
jednotlivé neterminály – A, B, C … X, Y, Z
řetězce neterminálů a terminálů – α, β, γ, …
prázdný řetězec značíme symbolem e nebo také ε

Chomského hierarchie

Chomského hierarchie vymezuje čtyři typy gramatik podle tvaru přepisovacích pravidel, jež obsahuje množina $P$ :

Typ 0 – Všechny formální gramatiky (neomezené gramatiky)
Typ 1 – Kontextové gramatiky
Typ 2 – Bezkontextové gramatiky
Typ 3 – Regulární gramatiky

Platí, že jazyky generované gramatikami typu 3 jsou podmnožinou jazyků generovaných gramatikami typu 2 atd.^[1]^[2]

Související články

Reference

↑ CHYTIL, Michal. Gramatiky a automaty. Praha: SNTL, 1983.
↑ MOLNÁR, Ľudovít; ČEŠKA, Milan; MELICHAR, Bořivoj. Gramatiky a jazyky. 3. vyd. Bratislava: Alfa, 1987.

[1] CHYTIL, Michal. Gramatiky a automaty. Praha: SNTL, 1983.

[2] MOLNÁR, Ľudovít; ČEŠKA, Milan; MELICHAR, Bořivoj. Gramatiky a jazyky. 3. vyd. Bratislava: Alfa, 1987.

[1]

[2]