- 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 Ax_{1}Ax_{2}for some strings x_{1}, x_{2}(T V)*, or*indirectly recursive*, that is, there is are variables X_{i}and productions

A...X_{1}...

X_{1}...X_{2}...

X_{2}...X_{3}...

...

X_{N}...A...

Copyright © 1996 by David Matuszek

Last modified Mar 20, 1996