Formální gramatika

V informatice se pojmem formální gramatika označuje struktura, 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:

S \longrightarrow aSb

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ů tak, že žádný symbol nepatří do $N$ a $\Sigma$ zároveň.
$P$ je konečná množina odvozovacích pravidel. Každé pravidlo je tvaru

(\Sigma \cup N)^{*} \longrightarrow (\Sigma \cup N)^{*}

$S$ je prvek z $N$ nazývaný počáteční symbol.

Podívejte se též na

Formální jazyky

Gourt Home::Gourt :: Formální gramatika

Formální definice

Podívejte se též na