Redukovaná gramatika

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ů.

Definice

Gramatika G je redukovaná, pokud každý neterminální symbol A vyhovuje podmínkám

$S\longrightarrow w_{1}Aw_{2}$ ,
existuje-li $x\in L(G)$ , že $w_{1}Aw_{2}\longrightarrow x$ .

kde $w_{1},w_{2}$ jsou libovolné řetězce.

Gramatiku G nazveme nejednoznačnou, pokud existuje řetězec $x\in L(G)$ , pro který existují dva různé způsoby odvození. Jinak nazveme gramatiku jednoznačnou.

Příklad redukované gramatiky

Mějme gramatiku $G=(N,\Sigma ,P,S)$ definovanou množinami
$N=\{S,A\}\,\!$
$T=\{a,b\}\,\!$
$P=\{S\longrightarrow aAa,A\longrightarrow bAb,A\longrightarrow a\}$ ,

potom řetězec $x=abbabba\in T$ je větou jazyka L(G), protože platí

$S\longrightarrow aAa\longrightarrow abAba\longrightarrow abbAbba\longrightarrow abbabba$ a tedy $S\longrightarrow x$ .

Z toho je vidět, že jazyk generovaný danou gramatikou je $L(G)=\{x|x=ab^{n}ab^{n}a,n=0,1,2...\}$ .

Zároveň vidíme, že gramatika je redukovaná, protože všechna přepisovací pravidla jsou typu $S\longrightarrow w_{1}Aw_{2}$ . Gramatika je jednoznačná, protože existuje pouze jeden způsob jak vygenerovat x.

Příklad neredukované gramatiky

Nechť $G=(N,\Sigma ,P,S)$ je gramatika definovaná množinami
$N=\{S,A\}\,\!$
$T=\{0,1\}\,\!$
$P=\{S\longrightarrow 01,S\longrightarrow 0S1,S\longrightarrow A,S\longrightarrow 1S0,S\longrightarrow SS\}$ ,

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

$S\longrightarrow 0S1\longrightarrow 0101$
$S\longrightarrow SS\longrightarrow 01S\longrightarrow 0101$

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