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. +more, 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“. +more 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. +more (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.

Související články

Formální jazyk * Noam Chomsky * Redukovaná gramatika

Reference

Kategorie:Formální jazyky