Викиконспекты - Вклад участника [ru]

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

2010-10-14T13:58:13Z

Boichenko:

{{Определение
|definition = Правила вида <tex>A \to \varepsilon</tex> называются <tex>\varepsilon</tex>-правилами.
}}

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

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

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

<tex>B \to zAz</tex>

<tex>A \to a \mid \varepsilon</tex>

Без <tex>\varepsilon</tex>-правил:

<tex>B \to zAz \mid zz</tex>

<tex>A \to a</tex>

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

<tex>B \to AzA</tex>

<tex>A \to a \mid \varepsilon</tex>

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

Итого, получаем грамматику без <tex>\varepsilon</tex>-правил:

<tex>B \to AzA \mid zA \mid Az \mid z</tex>

<tex>A \to a</tex>
----
Итак, приходим к следующему <big>'''алгоритму удаления <tex>\varepsilon</tex>-правил'''</big>:

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

<tex>B \to A</tex>

<tex>A \to \varepsilon</tex>

Получим:

<tex>B \to A \mid \varepsilon</tex>

== Ссылки ==
[http://eli.thegreenplace.net/2010/02/08/removing-epsilon-productions-from-context-free-grammars/ Реализация алгоритма на Python]

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

2010-10-14T13:47:47Z

Boichenko:

{{Определение
|definition = Правила вида <tex>A \to \varepsilon</tex> называются <tex>\varepsilon</tex>-правилами.
}}

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

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

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

<tex>B \to zAz</tex>

<tex>A \to a \mid \varepsilon</tex>

Без <tex>\varepsilon</tex>-правил:

<tex>B \to zAz \mid zz</tex>

<tex>A \to a</tex>

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

<tex>B \to AzA</tex>

<tex>A \to a \mid \varepsilon</tex>

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

Итого, получаем грамматику без <tex>\varepsilon</tex>-правил:

<tex>B \to AzA \mid zA \mid Az \mid z</tex>

<tex>A \to a</tex>
----
Итак, приходим к следующему '''алгоритму удаления <tex>\varepsilon</tex>-правил''':

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

<tex>B \to A</tex>

<tex>A \to \varepsilon</tex>

Получим:

<tex>B \to A \mid \varepsilon</tex>

== Ссылки ==
[http://eli.thegreenplace.net/2010/02/08/removing-epsilon-productions-from-context-free-grammars/ Реализация алгоритма на Python]

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

2010-10-14T13:31:48Z

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

{{Определение
|definition = Правила вида <tex>A \to \varepsilon</tex> называются <tex>\varepsilon</tex>-правилами.
}}

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

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

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

<tex>B \to zAz</tex>

<tex>A \to a \mid \varepsilon</tex>

Без <tex>\varepsilon</tex>-правил:

<tex>B \to zAz \mid zz</tex>

<tex>A \to a</tex>

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

<tex>B \to AzA</tex>

<tex>A \to a \mid \varepsilon</tex>

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

Итого, получаем грамматику без <tex>\varepsilon</tex>-правил:

<tex>B \to AzA \mid zA \mid Az \mid z</tex>

<tex>A \to a</tex>
----
Итак, приходим к следующему '''алгоритму удаления <tex>\varepsilon</tex>-правил''':

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

<tex>B \to A</tex>

<tex>A \to \varepsilon</tex>

Получим:

<tex>B \to A \mid \varepsilon</tex>