Definition 4.1.5: Let G = (V, _, P, S) be a context-free grammar. A symbol X__(V ___) is reachable if S _* _X_for some _,___(V ___)*; otherwise X is unreachable. A symbol X__V is live if X _* w for some w___*; otherwise X is dead. A symbol X__(V ___) is useless if it is either unreachable or dead.
Example 4.1.3.Consider the context-free grammar G with variables {S, A, B, C}, start = S, and productions
S _ bb | aB
A _ a | Aa
B _ bB | Ba | AB
C _ ba | aA | Bb | aCb
C is unreachable, and B is dead. A is both live andreachable and hence technically not useless, but itcontributes nothing to the language defined by G.
Previous slide | Next slide | Back to first slide | View graphic version |