Елиминација некорисних симбола

Елиминација некорисних симбола се одвија у два корака:

1. корак

У првом кораку се елиминишу они помоћни симболи X из којих се не може извести ниједна реч која се састоји од завршних симбола. Елиминација се врши на основу следећих рекурзивних дефиниција:

1. $X\in N$ је користан ако у граматици постоји бар једно правило облика $X\rightarrow x,\,x\in \Sigma ^{*}$
2. $X\in N$ је користан ако постоји бар једно правило такво да је $X\Rightarrow \alpha$, а α се састоји само од корисних симбола из N и симбола из Σ

Симболи који нису корисни се укљањају из скупа N и тако се добија нови скуп помоћних симбола N' и правила P'. Овако модификована граматика еквивалентна је полазној граматици.

2. корак

У другом кораку се елиминишу недоступни симболи из $\Sigma \cup N'$. Елиминација се врши на основу следећих рекурзивних правила:

1. $S\in N'$ је доступан симбол.
2. Симболи који се појављују на десној страни правила доступних симбола су доступни симболи.

Симболи који се не идентификују у овом кораку су недоступни, па се одстрањују из скупа N’, што даје нови скуп помоћних симбола N’’. Добијена граматика је еквивалентна полазној граматици.

Пример

Нека је граматика G над $\Sigma =\{a,\,b\}$, где је $N=\{S,\,A,\,B,\,C,\,D,\,E\}$, S почетни симбол, а скуп правила P:

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

$A\rightarrow a$

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

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

$D\rightarrow aC$

$E\rightarrow BA$

Према првом кораку, као корисни симболи прво се идентификују A и C, а затим још S и D. Тада, $N'=\{S,\,A,\,C,\,D\}$, а скуп правила P’ постаје:

$S\rightarrow CA$

$A\rightarrow a$

$C\rightarrow b$

$D\rightarrow aC$

У другом кораку биће елиминисан симбол D јер је недоступан из симбола S. Тада $N''=\{S,\,A,\,C\}$, а скуп правила P’’:

$S\rightarrow CA$

$A\rightarrow a$

$C\rightarrow b$

Погледајте још

• Лева рекурзија
• Елиминација е-правила
• Елиминација једноструких правила