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\rightarrow \epsilon \in P$. Svaki takav X se dodaje u skup A(G).
2. $X\in N$ je anulirajući postoji bar jedno pravilo $X\rightarrow \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\rightarrow \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 $\Sigma =\{(,\,)\}\,$ $N\,=\,\{S\}$, P :

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

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\rightarrow 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\rightarrow S\,|\,\epsilon$

gramatika sa novim skupom pravila opisuje isti jezik kao polazna.

Pogledajte još

• Leva rekurzija
• Eliminacija nekorisnih simbola
• Eliminacija jednostrukih pravila