Определение

Цепочка β (VT U VN)* непосредственно выводима из цепочки α (VT U VN)+ в грамматике G = {VT,VN,P, S} (обозначают),если

и правило вывода γ→δ содержится во множестве Р.

Пример 1

Рассмотрим грамматику G1, где множество правил вывода имеет вид: S→ aAb, aA→aaAb, A →ε. Цепочка aaAbb непосредственно выводима из цепочки aAb применением второго правила.

Определение

Цепочка β (VT U VN)* выводима из цепочки α (VT U VN)+ в грамматике G = {VT,VN,P, S} (обозначают α=> β) если существуют последовательность цепочек γ0,γ1… γn такая, что

α→γ0 →γ1→…→ γn-1 →γn= β

Последовательность γ0,γ1… γn называют выводом длины n.