Problem: L may be an infinite language.

We need two things:

- A systematic approach, so that we know we haven't overlooked any strings, and
- A way to stop after generating only a
*finite*number of strings -- knowing that, if we haven't generated w by now, we never will.

We can (almost) make the search finite by terminating every search path at the point that it generates a sentential form containing more than |w| terminals.

Copyright © 1996 by David Matuszek

Last modified Mar 2, 1996