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:
Each application of step 3 above is called a derivation step.
- 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,
Then we can write
- u and v are elements of (V
- x is an element of (V
- there is a production x
and we say that uxv directly derives uyv.
T : S derives T (or T is derived from S) in exactly one step.
T : S derives T in zero or more steps.
T : S derives T in one or more steps.
Copyright © 1996 by David Matuszek
Last modified Jan 29, 1996