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\to x,x\in {\mathrm{\Sigma }}^{\ast }$
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 $\mathrm{\Sigma }\cup N^{\prime }$. Eliminacija se vrši na osnovu sledećih rekurzivnih pravila:

1. $S\in N^{\prime }$ 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 $\mathrm{\Sigma }=\{a,b\}$, gde je $N=\{S,A,B,C,D,E\}$, -{S}- početni simbol, a skup pravila -{P}-:

$S\to AB|CA$

$A\to a$

$B\to AB|EA$

$C\to aB|b$

$D\to aC$

$E\to BA$

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

$S\to CA$

$A\to a$

$C\to b$

$D\to 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\to CA$

$A\to a$

$C\to b$

Види још

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