[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:
- 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.
Each application of step 3 above is called a derivation step.
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
Then we can write
uxv 
uyv
and we say that uxv directly derives uyv.
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