Eliminacija jednostrukih pravila

Neka je data KS-gramatika $G\,=\,(\Sigma ,\,N,\,P,\,S)$. Pretpostavimo da je u gramatici G nema nekorisnih simbola, ni ε-pravila. Postupak eliminacije jednostrukih pravila se svodi na postupak traženja svih izvođenja oblika:

$X\,\Rightarrow ^{*}\,Y,\,\,\,\,X,\,Y\in N.$

Ovaj postupak se vrši rekurzivno polazeći od jednostrukih pravila. Kad god se pronađe izvođenje gornjeg oblika, pravilima koja na levoj strani imaju X dodaju se desne strane svih pravila koja nisu jednostruka, a koja na levoj strani imaju simbol Y, dok se jednostruka Y-pravila uklanjaju. Ovako transformisana gramatika može imati nekorisnih simbola, koje treba eliminisati. Dobijena gramatika je ekvivalentna polaznoj gramatici, a nema nekorisnih simbola, kao ni jednostrukih ili ε-pravila.

Primer

U gramatici oslobođenoj od ε-pravila:

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

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

jedino jednostruko izvođenje je $T\Rightarrow S$. Zamenom simbola S na desnoj strani pravila (1) dosnom stranom pravila (2), dobija se sledeća gramatika bez jednostrukih pravila:

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

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

Pogledajte još

• Leva rekurzija
• Eliminacija nekorisnih simbola
• Eliminacija e-pravila