Derivation

Derivation --- вывод (в грамматике).

The concept of derivation is a central concept in the theory of formal grammars and languages. Let $G = (V_N, V_{T}, R, S)$ be a grammar and $\alpha, \beta$ be two strings over the alphabet $V= V_N \bigcup V_{T}$.

A derivation of $\beta$ from $\alpha$ in $G$ is a finite sequence of words over $V$

$w_{0}, w_{1}, \ldots, w_{j-1}, w_{j}, \ldots, w_{m},$

such that $m\geq 0$, $w_{0} = \alpha$, $w_{m}=\beta$ and for any $j \in [1, m]$, $w_{j-1}\Rightarrow w_{j}$, i.e. $w_{j}$ immediately derives from $w_{j-1}$. $m$ is called the length of the derivation.

Derivations are also written as

$w_{0}\Rightarrow w_{1}\Rightarrow \ldots, \Rightarrow w_{m}.$