Definition: Let G = (N, T, P, S) be a CFG. A symbol X Î N È T is accessible if there exist u, v Î S* such that S Þ* uXv; otherwise, X
is inaccessible.
Example:
Note: Each inaccessible symbol can be removed from
CFG
Accessible Symbols
Gist:
Symbol X is accessible if S Þ* …X…, where S is the start nonterminal.
S -
accessible: for u = e, v = e: S Þ0 S
G = ({S, A, B}, {a, b}, {S ® SB, S ® a, A ® ab, B ® aB }, S)
A -
inaccessible: there
is no u, v Î S* such that S Þ* uAv
B -
accessible: for u = S, v = e: S Þ1 SB
a - accessible:
for u = e, v = e:
S Þ1 a
b - inaccessible: there is no u, v Î
S* such that S Þ* ubv
27/31