Удаление eps-правил из грамматики

Определение:

Правила вида [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]