Redukovaná gramatika

Z Wikipedie, otevřené encyklopedie

Skočit na: Navigace, Hledání

Obsah

[editovat] 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 w1,w2 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.


[editovat] Příklad redukované gramatiky

Mějme gramatiku G = (N,Σ,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 abbAbba \longrightarrow abbabba a tedy S \longrightarrow x.


Z toho je vidět, že jazyk generovaný danou gramatikou je L(G) = {x | x = abnabna,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.


[editovat] Příklad neredukované gramatiky

Nechť G = (N,Σ,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, nebude řetězec terminální. Když toto pravidlo z gramatiky odebereme, dostaneme redukovanou gramatiku.

[editovat] Související články

Citováno z „http://cs.wikipedia.org/wiki/Redukovan%C3%A1_gramatika“