6
$\begingroup$

For which context-free grammars is it idempotent to remove $\varepsilon$-productions? Given that there are multiple rewriting algorithms which preserve language and leave the grammar without $\varepsilon$-productions (apart from $S \to \varepsilon$ iff $\varepsilon \in L(G)$), is this sensitive to the choice of algorithm?

As far as I can tell:

  • If $L(G) \not \ni \varepsilon$ then rewriting is always idempotent: the second pass finds no $\varepsilon$-productions to operate on.
  • If the start symbol doesn't occur on any right-hand-side it is always idempotent: after the first rewrite this property is maintained and there are no $\varepsilon$-productions except maybe $S \to \varepsilon$. The second pass may find an $\varepsilon$-production but since $S$ doesn't occur on any right-hand side there are no rules to transform.

Is there some variant of $\varepsilon$-removal which is always idempotent? Will treating the start symbol as never nullable (even if it is) produce an idempotent $\varepsilon$-removal algorithm? My tests suggest so, but I can't think of a proof at the moment.

$\endgroup$
1
$\begingroup$

Pretending the start symbol to not be nullable will lead to an $\varepsilon$-removal algorithm which is idempotent on all CFGs. I'll now formalize and prove this.

I define a non-terminal $A$ to be S-nullable iff

  • It is not $S$ (the start symbol); and
  • It either has a rule $A \to \varepsilon$ or it has a rule $A \to X_1 \ldots X_n$ where each $X_i$ is an S-nullable non-terminal.

The $\varepsilon$-removal algorithm then becomes:

Input: A context-free grammar $G = (N, \Sigma, S, P)$.

Output: A context-free grammar $G_\varepsilon$ with no S-nullable non-terminals and $L(G_\varepsilon) = L(G)$.

Procedure: let $G' = (N, \Sigma, S, P \setminus \{(A \to \varepsilon) \in P \mid A \not= S\})$. For each non-terminal $A$ in $N$ which is S-nullable in $G$, for each rule $B \to \alpha A \beta$ in $G'$, add the rule $B \to \alpha \beta$ to $G'$ if $\alpha \beta \not= \varepsilon$ or $B = S$ ($\alpha$ and $\beta$ are strings in $(N \cup \Sigma)^*$). Let $G_\varepsilon$ be $G'$ after all such rules have been added.

Note that one-by-one addition of rules means that if we have $S \to ABCd$ and $ABC$ is nullable and we nullify $A$, $B$, $C$ in that order, we will first add $S \to BCd$, then add $S \to ACd$ and $S \to Cd$, then add $S \to ABd \mid Bd \mid Ad \mid d$. In other words, it should be equivalent to doing the combinatorial expansion of rules one rule at a time.

Clearly $G_\varepsilon$ has no S-nullable rules: all $\varepsilon$ rules were removed (except $S \to \varepsilon$ if it was there), and no $\varepsilon$ rules were added (except maybe $S \to \varepsilon$). Hence no non-terminal is S-nullable directly (since $S$ is never S-nullable), and the inductive case has no basis to apply to.

Hence the algorithm is idempotent: it only adds or removes rules if there is an S-nullable non-terminal in $G$.

Also the algorithm preserves language, i.e. $L(G_\varepsilon) = L(G)$, by translation of derivations.

When we derive $A \Rightarrow \varepsilon$, we can instead avoid introducing $A$ in the first place, unless $A = S$ in which case $S \to \varepsilon$ is a rule. In the other direction, when we derive $\alpha \beta$ we can sprinkle it with (S-)nullable non-terminals and derive $\varepsilon$ from those.

Once more, with formality:

In one direction, when $\alpha \beta$ is derived from $A$ in $G_\varepsilon$ and $A \to \alpha \beta$ doesn't occur in $G$, this is because we added this rule based on finding $A \to \alpha B \beta$ with $B$ S-nullable. Either this rule occurs in $G$, in which case derive $\varepsilon$ from $B$, or this rule was itself added; let $\alpha' \beta' = \alpha B \beta$ such that we added $A \to \alpha' \beta'$ based on finding $A \to \alpha' C \beta'$ where $C$ is S-nullable.

Every inductive step searches for a right-hand side that's longer by 1 and bounded by the length of the longest rule in $G$, hence this process terminates. Derive $\varepsilon$ from all the back-filled non-terminals (they're all S-nullable). This will derive $\alpha \beta$ from $A$ in multiple steps, hence $\Rightarrow^*$ is preserved (in one direction).

In the other direction, if $\varepsilon$ is derived from $A$ (in a single step) where $A \to \varepsilon$ doesn't occur in $G_\varepsilon$, we know that $A \not= S$ (because we never remove $S \to \varepsilon$) and $A$ is S-nullable; hence we must have previously derived some sentential form containing $A$ in at least one derivation step.

Let $B \to \alpha A \beta$ be the rule which introduced the $A$ in question. If $\alpha \beta \not= \varepsilon$, we added the rule $B \to \alpha \beta$. Use this rule instead. (Any derivations performed between introducing and eliminating $A$ can still be performed, and have identical results.)

If $\alpha \beta = \varepsilon$, then either $B = S$ or $B$ is S-nullable. If $B = S$ we added the rule $S \to \varepsilon$; use this to replace the derivation $\gamma \underline{S} \delta \Rightarrow \gamma A \delta$ with $\gamma \underline{S} \delta \Rightarrow \gamma \delta$.

If $B \not= S$ it is S-nullable (as $B \Rightarrow A \Rightarrow \varepsilon$) and some other rule introduced $B$ to our sentential form. Apply the same replacement; the number of recursive steps is bounded above by the number of derivation steps done so far.

Unrelated observation: if in $G$ we have rules $S \to \varepsilon$ and $A \to \alpha S \beta$ then $G_\varepsilon$ will still have those rules, i.e. it will not be essentially non-contracting. However, if $S$ never occurs on the right-hand side of any rule in $G$, then $G_\varepsilon$ will be essentially non-contracting (and $S$ will also not occur on any right-hand side in $G_\varepsilon$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.