COT 6315 - Proof 11.3

COT6315 Formal Languages and Theory of Computation

R. E. Newman-Wolfe, University of Florida

Last modified 2/24/95.

Definition 11.2a: Live Variable

A variable A in V of grammer G = in CFG is live iff

Exists x in P(A)^T*, or
Exists alpha in P(A) and all variables in alpha are live.
No other variables are live.

Definition 11.2b: Reachable Variable

A variable A in V of grammer G = in CFG is reachable iff

Exists alpha1 A alpha2 in P(S), or
Exists reachable B and alpha1 A alpha2 in P(B).
No other variables are reachable.

Definition 11.2c: Useful Variable

A variable A in V of grammer G = in CFG is useful iff A appears in a derivation of a word in L(G), i.e.,

S =>* alpha1 A alpha2 =>* x in T*

If a variable is not useful, it is useless.

Algorithm 11.3a: FindLive(G)

    NL = {A | P(A) ^ T* <> 0 }
    REPEAT
       L = NL
       NL = L U {B in V | P(B) ^ (T U L)* <> 0 }
    UNTIL (L = NL)
    RETURN L

On iteration i, the algorithm adds those variables that take at least i steps to derive a string of terminals.

Algorithm 11.3b: FindReachable(G)

    NR = {S}
    REPEAT
       R = NR
       NR = R U {A in V | Exists B in R s.t. P(B) ^ (VUT)*A(VUT)* <> 0 }
    UNTIL (R = NR)
    RETURN R

On iteration i, the algorithm adds those variables that only appear in sentential forms that take least i steps to derive from S.

Algorithm 11.3: Elim-Useless(G)

    V' = FindLive(G)
    FOREACH (A in V1)
        P'(A) = P(A) ^ (V' U T)*
    G' = 
    V1 = FindReachable(G')
    FOREACH (A in V1)
        P1(A) = P(A) ^ (V1 U T)*
    RETURN

Only reachable and live variables can be useful (although these alone are not sufficient!), so the algorithm restricts attention to them. Only productions that involve live and reachable variables can contribute to L(G), so the rest are pruned. A variable may be both live and reachable, but may appear only in sentential forms with non-live variables, and so be useless. For this reason, it is important that the grammar G' with only live variables be produced first, since the pruning operation on P will eliminate all productions involving dead variables. If a live, reachable variable can only appear in a sentential form with non-live variables, then it will not be reachable in the pruned grammar, since the necessary step that produced the non-live variable(s) with which it must appear is no longer available.

Theorem 11.3: Equivalence of Grammar lacking Useless Variables

G in CFG and G1 = Elim-Useless(G) => L(G) = L(G1) and G1 has no useless variables.

Proof

Since only live variables can possibly produce a string of terminals, they are the only ones that can produce a string in L(G), so restricting V' to live variables cannot make L(G') different from L(G). Likewise, only reachable variables can appear in sentential forms derived from S in the grammar, and so any string in L(G) must have a derivation that has only reachable and live variables in its sentential forms. Thus L(G) = L(G1).

Showing that every variable A in V1 is useful is more involved. That A is both reachable and live is not enough. We must show that A appears in the derivation of some word x in L(G1). Since A is reachable in G', it must be that there are alpha and beta in (V' U T)* such that S =>* alpha A beta. Now all the variables in alpha and beta are live, so they can derive some terminal string, so it must be that there exist x1, x3 in T* such that alpha =>* x1 and beta =>* x3. Since A in V1, A is live, and there must be some x2 in T* such that A =>* x2. Thus S =>* alpha A beta =>* x1.x2.x3 = x in T*, so x in L(G1) and A is useful.

QED

Send comments to nemo@cis.ufl.edu