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⟶aSb$

2. $S⟶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: $\{ba,abab,aababb,aaababbb,...\}$

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,\mathrm{\Sigma },P,S)$, kde:

• $N$ je konečná množina neterminálních symbolů (neterminálů).
• $\mathrm{\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

  $(\mathrm{\Sigma }\cup N{)}^{*}N(\mathrm{\Sigma }\cup N{)}^{*}⟶(\mathrm{\Sigma }\cup N{)}^{*}$

• Šablona:Kotva $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

Šablona:Formální jazyky a gramatiky Šablona:Autoritní data