Derivation

Материал из WikiGrapp
Перейти к:навигация, поиск

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