Grammar Derivation

A Non-terminal $\beta$ is derived by Non-Terminal $\alpha$ if there is a series of Production Rules that can be applied to turn $\alpha$ into $\beta$

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)