COT6315 Formal Languages and Theory of Computation

R. E. Newman-Wolfe, University of Florida

Last modified 2/21/95.

Theorem 11.4: Equivalence of e-Productionless, Unit-Productionless Grammar lacking Useless Variables

G in CFG => Exists G' in CFG such that L(G') = L(G) - {e} and G' has no e-productions, no unit productions, and no useless variables.

Proof

Let G1 = Elim-e-Prod(G), G2 = Elim-Unit-Prod(G1), and G' = Elim-Useless(G2). From Theorems 11.1, 11.2, and 11.3, L(G) - {e} = L(G1) = L(G2) = L(G3). Since Elim-Unit-Prod adds no e-productions, and Elim-Useless adds no productions whatsoever, the progress made in constructing G1 and G2 is not lost along the way; no e-production or unit-productions are added so none appear in G'. G' of course has no useless variables by design, so we have the result.

QED

This document is copyright 1995 by Richard E. Newman-Wolfe.
Send comments to nemo@cis.ufl.edu