Вывод цепочек

Выводом называется процесс порождения предложения языка на основе правил определяющей язык грамматике. Чтобы дать формальное определение процессу вывода, необходимо ввести еще несколько дополнительных понятий.

Определение Цепочка b Î (V_TÈV_N) ^* непосредственно выводима из цепочки в грамматике (обозначается: a Þ b), если и , где , и правило вывода содержится во множестве Р.

Определение Цепочка b Î (V_TÈV_N) ^* выводима из цепочки в грамматике (обозначается a Þ* b), если существует последовательность цепочек (n ³ 0) такая, что .

Такая последовательность непосредственно выводимых цепочек называется выводом или цепочкой вывода.

Вывод называется правосторонним (левосторонним), если в нем на каждом шаге вывода правило грамматики применяется всегда к крайнему правому (левому) нетерминальному символу в цепочке.

Вывод можно рассматривать также как процесс получения одной строки из другой. С понятием вывода тесно связано понятие разбора строки языка. С одной стороны, разбор— это задача выяснения принадлежности заданной строки языку, порождае­мому заданной грамматикой. С другой стороны, разбор — это последовательность правил грамматики, определенным образом соответствующая выводу.

Пример Грамматика G ₁ = ({0, 1}, { A, S }, P₁, S), где множество Р состоит из правил вида: 1) S® 0 A 1;2)0 A® 00 A 1;3) A®e.

В грамматике G ₁ S Þ*000111, т.к. существует вывод .