Redukovaná gramatika

Obsah

1 Definice
2 Příklad redukované gramatiky
3 Příklad neredukované gramatiky
4 Podívejte se též na

[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 $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.

[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 = 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 \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] Podívejte se též na

Kategorie: Formální jazyky

Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „http://cs.wikipedia.org/wiki/Redukovan%C3%A1_gramatika“
Stránka byla naposledy upravena v Stránka byla naposledy editována 20. 8. 2008 v 20:11.
Veškerý text je dostupný za podmínek GNU Free Documentation License (Autorské právo pro podrobnosti).