Eliminacija jednostrukih pravila

Neka je data KS-gramatika $G=(\mathrm{\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\to S|ϵ$

(2) $S\to 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\to ϵ|S(S)|(S)|S()|()$

(2) $S\to S(S)|(S)|S()|()$

Pogledajte još

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