Derivation

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

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

A derivation of [math]\displaystyle{ \beta }[/math] from [math]\displaystyle{ \alpha }[/math] in [math]\displaystyle{ G }[/math] is a finite sequence of words over [math]\displaystyle{ V }[/math]

[math]\displaystyle{ w_{0}, w_{1}, \ldots, w_{j-1}, w_{j}, \ldots, w_{m}, }[/math]

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

Derivations are also written as

[math]\displaystyle{ w_{0}\Rightarrow w_{1}\Rightarrow \ldots, \Rightarrow w_{m}. }[/math]