[Overview] [Previous] [Next]

Preliminary Definitions

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 containing itself. For example, variable A is recursive if
S derives uAy
for some values of u and y.

A recursive variable A can be either

Copyright 1996 by David Matuszek
Last modified Mar 20, 1996