Suppose language L is defined by a grammar G = (V, T, S, P). You can find a string belonging to this language as follows:

- Start with a string
*w*consisting of only the start symbol S. - Find a substring
*x*of*w*that matches the left-hand side of some production p in P. - Replace the substring
*x*of*w*with the right-hand side of production p. - Repeat steps 2 and 3 until the string consists entirely of symbols of T (that is, it doesn't contain any variables).
- The final string belongs to the language L.

Suppose *w* is a string that can be written as *uxv*,

where

*u*and*v*are elements of (V T)*x*is an element of (V T)- there is a production
*x**y*

and we say that

Notation:

- S T : S derives T (or T is derived from S) in exactly one step.
- S T : S derives T in zero or more steps.
- S T : S derives T in one or more steps.

Copyright © 1996 by David Matuszek

Last modified Jan 29, 1996