Преобразования грамматик, нормальные формы грамматик

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

Символ x  (Vt  Vn) называется недостижимым в грамматике G, если он не появляется ни в одной сентенциальной форме этой грамматики.

Cимвол A  Vn называется бесплодным в грамматике G = (Vt, Vn, P, S), если множество {  Vt^* | A  } пусто.

Грамматика G называется приведенной, если в ней нет недостижимых и бесплодных символов.

Алгоритм приведения грамматики:

1. обнаруживаются и удаляются все бесплодные нетерминалы;

1. обнаруживаются и удаляются все недостижимые символы.

Удаление символов сопровождается удалением правил вывода, содержащих эти символы.

NB: если в этом алгоритме переставить шаги (1) и (2), то не всегда результатом будет приведенная грамматика.

Для любой КС-грамматики G существует эквивалентная ей грамматика G’ с правилами вида A  BC или A  a (бинарные правила, бинарное дерево вывода).

Грамматика G’ представлена в нормальной форме Хомского.

Пример:

G = ({a, b, c}, {C, S}, R1, S) и G’ = ({a, b, c}, {A, B, C, D, E, S}, R2, S)

R1: S  aCbb R2: S  DE, D  AC, E  BB, C  DE,

C  aCbb A  a, B  b, C  c

C  c

L(G) = L(G’) = {aⁿ c b²ⁿ | n>0}

Дерево вывода:

S

D E

C

D E

A A C B B B B

a a c b b b b

Для любой КС-грамматики G существует эквивалентная ей грамматика G’ с правилами вида A  a (где A  Vn, a  Vt,  – цепочка на алфавите Vn  #). Грамматика G’ представлена в нормальной форме Грейбах.

Пример:

G = ({a, b, c}, {C, S}, R1, S) и G’ = ({a, b, c}, {B, C, S}, R2, S)

R1: S  aCbb R2: S  aCBB, С  aCBB,

C  aCbb B  b, C  c

C  c

L(G) = L(G’) = {aⁿ c b²ⁿ | n>0}

Дерево вывода:

S

C

C B B B B

a a c b b b b

Алгоритмы перебор и методы его сокращения Перебор с возвратом (Общая схема)

Даны N упорядоченных множеств U₁, U₂, ..., U_N (N - известно), и требуется построить вектор A=(a₁, a₂, ..., a_N), где a₁U₁, a₂U₂, ..., a_NU_N, удовлетворяющий заданному множеству условий и ограничений.

В алгоритме перебора вектор А строится покомпонентно слева направо. Предположим, что уже найдены значения первых (k-1) компонент, А=(а₁, а₂, ..., а_(k-1), ?, ..., ?), тогда заданное множество условий ограничивает выбор следующей компоненты а_k некоторым множеством S_kU_k.

Если S_k<>[ ] (пустое), мы вправе выбрать в качестве а_k наименьший элемент S_k и перейти к выбору (k+1) компоненты и так далее.

Однако если условия таковы, что S_k оказалось пустым, то мы возвращаемся к выбору (k-1) компоненты, отбрасываем а_(k-1) и выбираем в качестве нового а_(k-1) тот элемент S_(k-1), который непосредственно следует за только что отброшенным.

Может оказаться, что для нового а_(k-1) условия задачи допускают непустое S_k, и тогда мы пытаемся снова выбрать элемент а_k. Если невозможно выбрать а_(k-1), мы возвращаемся еще на шаг назад и выбираем новый элемент а_(k-2) и так далее.

Графическое изображение - дерево поиска. Корень дерева (0 уровень) есть пустой вектор.

Его сыновья суть множество кандидатов для выбора а₁, и, в общем случае, узлы k-го уровня являются кандидатами на выбор а_k при условии, что а₁, а₂, ..., а_(k-1) выбраны так, как указывают предки этих узлов. Вопрос о том, имеет ли задача решение, равносилен вопросу, являются ли какие-нибудь узлы дерева решениями. Разыскивая все решения, мы хотим получить все такие узлы.