[Overview] [Previous] [Next]

Derivations

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,
where

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

Notation:



Copyright 1996 by David Matuszek
Last modified Jan 29, 1996