Eliminacija ε-pravila

Ukoliko gramatika poseduje ε-pravila, može se dogoditi da tokom izvođenja dužina rečeničnih formi počne da opada, a poželjno je, zbog potreba analize, izbeći ovakvu situaciju. U postupku eliminacije ε-pravila iz kontekstno slobodne gramatike podrazumeva se da je iz jezika eventualno odstranjena prazna reč ε.

Algoritam eliminacije

Za zadatu gramatiku -{G}-, postupak se sastoji iz dva koraka:

1. kostrukcije skupa $A(G)\subseteq N$ anulirajućih simbola, tj. skupa pomoćnih simbola koji se mogu prepisati kao prazna reč.
2. transformacije pravila koja sadrže anulirajuće simbole

1. korak

Za datu KS-gramatiku -{G}- bez nekorisnih simbola, skup anulirajućih simbola -{A(G)}-, inicijalno prazan, se dobija primenom sledećih rekurzivnih pravila:

1. $X\in N$ je anulirajući ako je $X\to ϵ\in P$. Svaki takav X se dodaje u skup -{A(G)}-.
2. $X\in N$ je anulirajući postoji bar jedno pravilo $X\to \alpha \in P$ gde su svi pomoćni simboli u niski α anulirajući. ( $\alpha \in N^{*}$)

2. korak

Kada je određen skup -{A(G)}-, modifikuju se pravila gramatike -{G}- koja sadrže anulirajuće simbole tako što se u svakom pravilu $X\to \alpha \in P$ u niski α zamene anulirajući simboli praznom reči ε na sve moguće načine, a zatim se odstrane ε-pravila. KS-gramatika koja se dobija kao rezultat ove transformacije je ekvivalentna polaznoj gramatici do na praznu reč.

Primer

Neka je gramatika G nad $\mathrm{\Sigma }=\{(,)\}$ $N=\{S\}$, -{P}- :

$S\to S(S)|ϵ$

Jedini neterminal -{S}- je i anulirajući. U niski α = -{S(S)}- zamenjujemo simbol -{S}- sa ε na sve moguće načine što daje novo pravilo:

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

koje opisuje isti jezik ali bez prazne reči. U skladu sa definicijom, gramatika se može modifikovati uvođenjem novog početnog simbola -{T}- umesto -{S}- i dodavanjem novog pravila:

$T\to S|ϵ$

gramatika sa novim skupom pravila opisuje isti jezik kao polazna.

Pogledajte još

• Leva rekurzija
• Eliminacija nekorisnih simbola
• Eliminacija jednostrukih pravila