From Wikipedia, the free encyclopedia
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:
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.
Gramatika G je čtveřice , kde:
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]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.