Выводимость цепочки

Говорят, что Цепочка $\gamma$ выводится из цепочки $\delta$ в грамматике $G=(\Gamma ,\Sigma ,P,S)$, если

• либо $\gamma =\delta$
• либо существует последовательность цепочек $\delta ={\mu }_0,{\mu }_1,\dots ,{\mu }_n=\gamma$ таких, что каждая последующая цепочка непосредственно выводится из предыдущей цепочки:

$${\mu }_0\Rightarrow {\mu }_1\Rightarrow \cdots \Rightarrow {\mu }_n$$

Такая последовательность также называется выводом цепочки $\gamma$ из цепочки $\delta$.

Обозначение вывода:

$$\delta {\Rightarrow }^{\ast }\gamma$$