[Overview] [Previous] [Next]


Productions are rules that can be used to define the strings belonging to a language.

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

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

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

Then we can write
uxv directly derives uyv
and we say that uxv directly derives uyv.


Copyright 1996 by David Matuszek
Last modified Jan 29, 1996