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:

1.

2.

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:

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

[editovat] Formální definice

Gramatika G je čtveřice (N,Σ,P,S), kde:

• N je konečná množina neterminálních symbolů (neterminálů).
• Σ je konečná množina terminálních symbolů tak, že žádný symbol nepatří do N a Σ zároveň. (Obvykle se značí řeckým písmenkem sigma.)
• P je konečná množina odvozovacích pravidel. Každé pravidlo je tvaru

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

[editovat] Podívejte se též na

• Formální jazyk
• Noam Chomsky
• Chomského hierarchie