Cesko.wiki Redukovaná gramatika
Author
Albert FloresRedukovaná 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_1Aw_2, * existuje-li x \in L(G), že w_1Aw_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^nab^na, n= 0,1,2...\}.
Zároveň vidíme, že gramatika je redukovaná, protože všechna přepisovací pravidla jsou typu S \longrightarrow w_1Aw_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. +more Když toto pravidlo z gramatiky odebereme, dostaneme redukovanou gramatiku.