Formální gramatika

(přesměrováno z Neterminál)

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 '', počáteční symbol je '' a pravidla jsou definována takto:

1.
2.

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

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

Formální definice

editovat

Gramatika G je čtveřice  , kde:

  •   je konečná množina neterminálních symbolů (neterminálů).
  •   je konečná množina terminálních symbolů disjunktní od  . (Obvykle se značí řeckým písmenkem sigma.)
  •   je konečná množina přepisovacích pravidel. Každé pravidlo je tvaru
     
  •   je prvek z   nazývaný počáteční symbol.

Konvence

editovat
  • 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

editovat

Chomského hierarchie vymezuje čtyři typy gramatik podle tvaru přepisovacích pravidel, jež obsahuje množina  :

Platí, že jazyky generované gramatikami typu 3 jsou podmnožinou jazyků generovaných gramatikami typu 2 atd.[1][2]

Související články

editovat

Reference

editovat
  1. CHYTIL, Michal. Gramatiky a automaty. Praha: SNTL, 1983. 
  2. MOLNÁR, Ľudovít; ČEŠKA, Milan; MELICHAR, Bořivoj. Gramatiky a jazyky. 3. vyd. Bratislava: Alfa, 1987.