3
правки
Изменения
Новая страница: «{{Определение |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>. <br />То есть, язык порождаемый грамматикой <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>)<br /> Если <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>
|definition = Правила вида <tex>A \to \varepsilon</tex> называются <tex>\varepsilon</tex>-правилами.
}}
По данной произвольной КС-грамматике <tex>G</tex> можно построить новую КС-грамматику <tex>G_1</tex> без <tex>\varepsilon</tex>-правил, эквивалентную исходной без терминала <tex>\varepsilon</tex>. <br />То есть, язык порождаемый грамматикой <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>)<br /> Если <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>
