Grammar Derivation

The set of Production Rules that can be applied to Non-terminal $\alpha$ into Non-terminal $\beta$.

• Can be thought of as a path in a Parse Tree

Formal Definition

• Let $\alpha ,\beta \in (V\cup \Sigma {)}^{\ast }$
• A derivation of $\beta$ from $\alpha$ in Grammar $G$ is the series of strings $s_1,\dots ,s_n$ where:
  • $s_1=\alpha$
  • $s_n=\beta$
  • $s_i{\Rightarrow }_G{s}_{i+1}$ (Each string has a Production to the next one)