Елиминација ε-правила

Уколико граматика поседује ε-правила, може се догодити да током извођења дужина реченичних форми почне да опада, а пожељно је, због потреба анализе, избећи овакву ситуацију. У поступку елиминације ε-правила из контекстно слободне граматике подразумева се да је из језика евентуално одстрањена празна реч ε.

Алгоритам елиминације

За задату граматику G, поступак се састоји из два корака:

1. кострукције скупа $A(G)\subseteq N$ анулирајућих симбола, тј. скупа помоћних симбола који се могу преписати као празна реч.
2. трансформације правила која садрже анулирајуће симболе

1. корак

За дату КС-граматику G без некорисних симбола, скуп анулирајућих симбола A(G), иницијално празан, се добија применом следећих рекурзивних правила:

1. $X\in N$ је анулирајући ако је $X\rightarrow \epsilon \in P$. Сваки такав X се додаје у скуп A(G).
2. $X\in N$ је анулирајући постоји бар једно правило $X\rightarrow \alpha \in P$ где су сви помоћни симболи у ниски α анулирајући. ( $\alpha \in N^{*}$)

2. корак

Када је одређен скуп A(G), модификују се правила граматике G која садрже анулирајуће симболе тако што се у сваком правилу $X\rightarrow \alpha \in P$ у ниски α замене анулирајући симболи празном речи ε на све могуће начине, а затим се одстране ε-правила. КС-граматика која се добија као резултат ове трансформације је еквивалентна полазној граматици до на празну реч.

Пример

Нека је граматика Г над $\Sigma =\{(,\,)\}\,$ $N\,=\,\{S\}$, P :

$S\rightarrow S(S)\,|\,\epsilon$

Једини нетерминал S је и анулирајући. У ниски α = S(S) замењујемо симбол S са ε на све могуће начине што даје ново правило:

$S\rightarrow S(S)\,|\,(S)\,|\,S()\,|\,()$

које описује исти језик али без празне речи. У складу са дефиницијом, граматика се може модификовати увођењем новог почетног симбола T уместо S и додавањем новог правила:

$T\rightarrow S\,|\,\epsilon$

граматика са новим скупом правила описује исти језик као полазна.

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

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