Проблема принадлежности

Необходимо определить является ли цепочка z элементом языка L(G). Для КС-языков эта проблема разрешима.

Алгоритм: Рассмотреть все синтаксикальные формы грамматики G, имеющие длину, равную длине этой цепочки. Если ни одна из этих цепочек не является строкой z, то zËL(G).

Эффективное решение проблемы выводимости возможно лишь в случае наложения ряда ограничений на определение КС-грамматики.

Вопросы и упражнения

Каким методом определяется принадлежность цепочки языку?

Нормальная форма Грейбаха

Грамматика G находится в нормальной форме Грейбаха, если все правила G имеют вид A®aa, где а – терминальный символ, а a – цепочка, состоящая их терминалов и нетерминалов, а также пустой цепочки:

"x [xÎaÞ xÎTÈNÈ{e}].

Изменение правил грамматики надо производить так, чтобы первоначальный и конечный языки совпадали.

Теорема 1: Если в грамматике есть правило А®a₁Ba₂ и правило В®b, то эти правила можно заменить эквивалентным правилом вида А®a₁ba₂.

Замечание: если А®a₁Ba₂ и В®b₁|b₂|…|b_n, то А®a₁b₁a₂|a₁b₂a₂|…|a₁b_na₂.

Правила вида А®Аa называются рекурсивными слева.

Теорема 2: Устранение рекурсивных слева правил. Если в грамматике G имеется правило А®Аa и А®b, то эти правила можно эквивалентно заменить правилами А®b|bA’ и А’®a|aA’.

Доказательство: Рассмотрим, какие цепочки порождают первые правила. А®Аa®Аa²®*Aa^m, где m³1. А®*ba^m, где m³0.

Покажем, что с помощью эквивалентных правил получаем те же цепочки.

A'®aA’®a²A’®*a^m, где m³1. A®bA’®*ba^m, где m³0.

Замечание: Если А®Аa и А®b₁|b₂|…|b_n, то А???(то А®b₁A’|b₂A’|…|b_n A’.)

Теорема 3: Для любого e-свободного КС-языка можно определить КС-грамматику в нормальной форме Грейбаха. При этом язык сохраняется.

Алгоритм:

G: S®AS|AB

A®BS|a

B®AA|b

Шаг 1: Нумерация нетерминалов. {S, A, B} ~ {A₁, A₂, A₃}

G: A₁® A₂ A₁| A₂ A₃

A₂® A₃ A₁|a