Redukovaná gramatika

Šablona:Bez zdrojů 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⟶w_{1}A{w}_2$,
• existuje-li $x\in L(G)$, že $w_{1}A{w}_2⟶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,\mathrm{\Sigma },P,S)$ definovanou množinami

$N=\{S,A\}$

$T=\{a,b\}$

$P=\{S⟶aAa,A⟶bAb,A⟶a\}$,

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

$S⟶aAa⟶abAba⟶abbAbba⟶abbabba$ a tedy $S⟶x$.

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

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

Příklad neredukované gramatiky

Nechť $G=(N,\mathrm{\Sigma },P,S)$ je gramatika definovaná množinami

$N=\{S,A\}$

$T=\{0,1\}$

$P=\{S⟶01,S⟶0S1,S⟶A,S⟶1S0,S⟶SS\}$,

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

• $S⟶0S1⟶0101$
• $S⟶SS⟶01S⟶0101$

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

Související články

• Formální jazyk
• Formální gramatika