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 '${\displaystyle a}$' a '${\displaystyle b}$', počáteční symbol je '${\displaystyle S}$' a pravidla jsou definována takto:

1. ${\displaystyle S\longrightarrow aSb}$

2. ${\displaystyle S\longrightarrow ba}$

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

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

Formální definice

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

• ${\displaystyle N}$ je konečná množina neterminálních symbolů (neterminálů).
• ${\displaystyle \Sigma }$ je konečná množina terminálních symbolů disjunktní od ${\displaystyle N}$. (Obvykle se značí řeckým písmenkem sigma.)
• ${\displaystyle P}$ je konečná množina přepisovacích pravidel. Každé pravidlo je tvaru

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

• ${\displaystyle S}$ je prvek z ${\displaystyle 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 ${\displaystyle 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

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

Reference