[Overview] [Previous] [Next]
A variable is useful if it occurs in the derivation
of some string.
This requires that
A variable is recursive if it can generate a string
For example, variable A is recursive if
for some values of u and y.
- the variable occurs in some sentential form (you can get
to the variable if you start from S), and
- a string of terminals can be derived from the sentential form
(the variable isn't a "dead end").
A recursive variable A can be either
- directly recursive, that is, there is a production Ax1Ax2
for some strings x1, x2
(T V)*, or
- indirectly recursive, that is, there is are
variables Xi and productions
Copyright © 1996 by David Matuszek
Last modified Mar 20, 1996