[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

• 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.