Tento článek není dostatečně
ozdrojován, a může tedy obsahovat informace, které je třeba
ověřit.
Jste-li s popisovaným předmětem seznámeni, pomozte doložit uvedená tvrzení doplněním
referencí na
věrohodné zdroje.
Redukovaná gramatika je taková gramatika, která je bez nedosažitelných neterminálů a kde každý neterminál má konečný rozvoj, tj. každý neterminál A gramatiky lze přepsat na řetězec terminálních symbolů.
Gramatika G je redukovaná, pokud každý neterminální symbol A vyhovuje podmínkám
,
- existuje-li
, že
.
kde
jsou libovolné řetězce.
Gramatiku G nazveme nejednoznačnou, pokud existuje řetězec
, pro který existují dva různé způsoby odvození. Jinak nazveme gramatiku jednoznačnou.
Mějme gramatiku
definovanou množinami


,
potom řetězec
je větou jazyka L(G), protože platí
a tedy
.
Z toho je vidět, že jazyk generovaný danou gramatikou je
.
Zároveň vidíme, že gramatika je redukovaná, protože všechna přepisovací pravidla jsou typu
. Gramatika je jednoznačná, protože existuje pouze jeden způsob jak vygenerovat x.
Nechť
je gramatika definovaná množinami


,
G je nejednoznačná, protože větu 0101 lze odvodit dvěma různými způsoby


G je neredukovaná, protože obsahuje pravidlo
. Pokud toto pravidlo aplikujeme, nelze již vygenerovat terminální řetězec. Když toto pravidlo z gramatiky odebereme, dostaneme redukovanou gramatiku.