Definition: Let G = (N, T, P, S) be a CFG. A symbol X Î N È T is terminating if there exists w Î T* such that X Þ* w; otherwise, X
is nonterminating
Example:
Note: Each nonterminating symbol can be removed from any CFG.
Terminating Symbols
Gist:
Symbol X is terminating if X derives a
terminal string.
Symbol S - terminating: for w = a: S Þ1 a
G = ({S, A, B}, {a, b}, {S ® SB, S ® a, A ® ab, B ® aB }, S)
Symbol A - terminating: for w = ab: A
Þ1 ab
Symbol B - nonterminating: there is no w Î T* such that B
Þ* w
Symbol a - terminating: for
w = a : a Þ0 a
Symbol b - terminating: for w = b : b Þ0 b
28/31