Definition 4.3.1: A production _______is referred to as an erasing production if len(_) < len(_). For context-free grammars these productions necessarily take the form A ____ for some variable A.
Theorem 4.3.1: If L is a context-free language, then there exists a context-free grammar G with no erasing rules so that L(G) = L-{_}. If L ° _ and L° {_}, G may be chosen to have no useless symbols.
The inductively defined sets of variables E1 = {A_V | A______P}, and for iŤ1, Ei+1 = Ei _ {A_ V | A_ _ _ P and __Ei*} effectively provide an algorithm to compute erasing.
| Previous slide | Next slide | Back to first slide | View graphic version |