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

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

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

Gramatiku G nazveme nejednoznačnou, pokud existuje řetězec ${\displaystyle 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 ${\displaystyle G=(N,\Sigma ,P,S)}$ definovanou množinami
${\displaystyle N=\{S,A\}\,\!}$
${\displaystyle T=\{a,b\}\,\!}$
${\displaystyle P=\{S\longrightarrow aAa,A\longrightarrow bAb,A\longrightarrow a\}}$,

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

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

Z toho je vidět, že jazyk generovaný danou gramatikou je ${\displaystyle 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 ${\displaystyle 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ť ${\displaystyle G=(N,\Sigma ,P,S)}$ je gramatika definovaná množinami
${\displaystyle N=\{S,A\}\,\!}$
${\displaystyle T=\{0,1\}\,\!}$
${\displaystyle 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

• ${\displaystyle S\longrightarrow 0S1\longrightarrow 0101}$
• ${\displaystyle S\longrightarrow SS\longrightarrow 01S\longrightarrow 0101}$

G je neredukovaná, protože obsahuje pravidlo ${\displaystyle S\longrightarrow 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

Zdroj