Процесс порождения

Порождающая грамматика позволяет получить (породить) все цепочки символов определяемого ею языка следующим образом.

Порождение всегда начинается с одного из начальных символов грамматики, пусть это будет S₁. Среди всех правил множества P применяется правило, в котором левая часть (слева от стрелки) состоит только из одного символа S₁, и эта левая часть заменяется на правую. Затем среди полученной цепочки символов находится такая ее часть (подцепочка), которая совпадает с левой частью какого-либо из правил множества P, и делается еще одна подстановка и т.д. Процесс заканчивается, если в полученной после всех подстановок цепочке больше не найдется ни одной части, совпадающей с левой частью ни одного из правил множества P.

Если в полученной таким образом цепочке все символы принадлежат алфавиту языка Σ, то считается, что вся порожденная цепочка принадлежит языку L. Если же в этой цепочке присутствует хотя бы один символов алфавита грамматики N, то такая цепочка не может принадлежать языку L. В этом случае говорят, что процесс порождения зашел в тупик. Может случиться, что процесс порождения никак не может остановиться, какие бы правила ни применялись на очередном шаге. Тогда говорят, что процесс порождения зациклил (попал в бесконечный цикл).

Символы алфавита языка Σ имеют еще одно название – терминальные символы (или просто терминалы), потому что получившаяся цепочка, состоящая только из них, прекращает процесс порождения. В свою очередь, символы алфавита грамматики N также имеют другое название – нетерминальные символы (или просто нетерминалы).

Дата добавления: 2015-07-26; просмотров: 153; Нарушение авторских прав

Мы поможем в написании ваших работ!