Useless Symbols

e.g.

B is useless because

D is useless because

Def. A symbol X is useful if
\ for

Two aspects:

1. , (live)
2. (reachable)

Algorithm to remove those variable which can not produce strings of terminals


While do

e.g.
because
is useless.

Algorithm to identify


Iteratively, if
and
then add all the variables of to V'
and all the terminals of to T'.

e.g.

1. 
2. because
3. because

Thus, D is useless.

Simplified Grammar is:

Must apply algorithm for first.

e.g.



useless

A useless

Otherwise, applying these two algorithms in reverse:

no useless symbols found.

useless
still remains.