Удаление eps-правил из грамматики — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |definition = Правила вида <tex>A \to \varepsilon</tex> называются <tex>\varepsilon</tex>-правилами. }} По …»)
(нет различий)

Версия 16:31, 14 октября 2010

Определение:
Правила вида [math]A \to \varepsilon[/math] называются [math]\varepsilon[/math]-правилами.


По данной произвольной КС-грамматике [math]G[/math] можно построить новую КС-грамматику [math]G_1[/math] без [math]\varepsilon[/math]-правил, эквивалентную исходной без терминала [math]\varepsilon[/math].
То есть, язык порождаемый грамматикой [math]G: L(G)=L(G_1) - \{\varepsilon\}[/math].


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


1. C [math]\varepsilon[/math]-правилами: (Здесь и далее [math]a, b, c, .. -[/math] терминалы; [math]A, B, C, .. -[/math] нетерминалы; [math]z, y, x .. -[/math] произвольные строки из теминалов и нетеминалов)

[math]B \to zAz[/math]

[math]A \to a \mid \varepsilon[/math]

Без [math]\varepsilon[/math]-правил:

[math]B \to zAz \mid zz[/math]

[math]A \to a[/math]


2. Более интересный пример - [math]\varepsilon[/math]-порождающий терминал [math]A[/math] встречается в продукции несколько раз:

[math]B \to AzA[/math]

[math]A \to a \mid \varepsilon[/math]

Если удаляется [math]\varepsilon[/math]-правило [math]A \to \varepsilon[/math], то каждую продукцию ,содержащую [math]A[/math] справа, следует заменить на [math]2^k[/math] продукций, где [math]k[/math] - число встреченных в продукции [math]A[/math], так как каждое такое [math]A[/math] может находиться в 2ух состояниях - есть оно в продукции или же нет. Да, из этих [math]2^k[/math] продукций могут быть повторения, нужно попытаться найти их и удалить лишние.

Итого, получаем грамматику без [math]\varepsilon[/math]-правил:

[math]B \to AzA \mid zA \mid Az \mid z[/math]

[math]A \to a[/math]


Итак, приходим к следующему алгоритму удаления [math]\varepsilon[/math]-правил:

  1. Пока есть [math]\varepsilon[/math]-правило.(Обозначим его за [math]A \to \varepsilon[/math])
    Если [math]A[/math] - стартовое состояние - ничего не делаем и переходим к пункту 1.
  2. Удалить его
  3. Каждую продукцию ,содержащую справа [math]A[/math] заменяем на [math]2^k[/math] продукций, как в примере 2. Переход к пункту 1.

Заметим, что на 3ем пункте мы можем породить еще одно [math]\varepsilon[/math]-правило, например:

[math]B \to A[/math]

[math]A \to \varepsilon[/math]

Получим:

[math]B \to A \mid \varepsilon[/math]