Eliminacija nekorisnih simbola

Eliminacija nekorisnih simbola se odvija u dva koraka:

1. korak

U prvom koraku se eliminišu oni pomoćni simboli X iz kojih se ne može izvesti nijedna reč koja se sastoji od završnih simbola. Eliminacija se vrši na osnovu sledećih rekurzivnih definicija:

1. $X\in N$ je koristan ako u gramatici postoji bar jedno pravilo oblika $X\rightarrow x,\,x\in \Sigma ^{*}$
2. $X\in N$ je koristan ako postoji bar jedno pravilo takvo da je $X\Rightarrow \alpha$, a α se sastoji samo od korisnih simbola iz N i simbola iz Σ

Simboli koji nisu korisni se ukljanjaju iz skupa N i tako se dobija novi skup pomoćnih simbola N' i pravila P'. Ovako modifikovana gramatika ekvivalentna je polaznoj gramatici.

2. korak

U drugom koraku se eliminišu nedostupni simboli iz $\Sigma \cup N'$. Eliminacija se vrši na osnovu sledećih rekurzivnih pravila:

1. $S\in N'$ je dostupan simbol.
2. Simboli koji se pojavljuju na desnoj strani pravila dostupnih simbola su dostupni simboli.

Simboli koji se ne identifikuju u ovom koraku su nedostupni, pa se odstranjuju iz skupa N’, što daje novi skup pomoćnih simbola N’’. Dobijena gramatika je ekvivalentna polaznoj gramatici.

Primer

Neka je gramatika G nad $\Sigma =\{a,\,b\}$, gde je $N=\{S,\,A,\,B,\,C,\,D,\,E\}$, S početni simbol, a skup pravila P:

$S\rightarrow AB\,|\,CA$

$A\rightarrow a$

$B\rightarrow AB\,|\,EA$

$C\rightarrow aB\,|\,b$

$D\rightarrow aC$

$E\rightarrow BA$

Prema prvom koraku, kao korisni simboli prvo se identifikuju A i C, a zatim još S i D. Tada, $N'=\{S,\,A,\,C,\,D\}$, a skup pravila P’ postaje:

$S\rightarrow CA$

$A\rightarrow a$

$C\rightarrow b$

$D\rightarrow aC$

U drugom koraku biće eliminisan simbol D jer je nedostupan iz simbola S. Tada $N''=\{S,\,A,\,C\}$, a skup pravila P’’:

$S\rightarrow CA$

$A\rightarrow a$

$C\rightarrow b$

Pogledajte još

• Leva rekurzija
• Eliminacija e-pravila
• Eliminacija jednostrukih pravila