Удаление длинных правил из грамматики — различия между версиями
м (→Пример работы) |
м (→Алгоритм) |
||
Строка 10: | Строка 10: | ||
== Алгоритм == | == Алгоритм == | ||
С каждым длинным правилом <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>, <tex>k > 2</tex>, <tex>a_i \in \Sigma \cup N</tex> проделаем следующее: <br> | С каждым длинным правилом <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>, <tex>k > 2</tex>, <tex>a_i \in \Sigma \cup N</tex> проделаем следующее: <br> | ||
− | Добавим в грамматику <tex>k-2</tex> новых нетерминала <tex>B_1, B_2, \ldots B_{k-2}</tex>. <br> | + | #Добавим в грамматику <tex>k-2</tex> новых нетерминала <tex>B_1, B_2, \ldots B_{k-2}</tex>. <br> |
− | Добавим в грамматику <tex>k-1</tex> новое правило: <br> | + | #Добавим в грамматику <tex>k-1</tex> новое правило: <br> |
− | <tex>A \rightarrow a_1B_1</tex>, <br> | + | #:<tex>A \rightarrow a_1B_1</tex>, <br> |
− | <tex>B_1 \rightarrow a_2B_2</tex>, <br> | + | #:<tex>B_1 \rightarrow a_2B_2</tex>, <br> |
− | <tex>B_2 \rightarrow a_3B_3</tex>, <br> | + | #:<tex>B_2 \rightarrow a_3B_3</tex>, <br> |
− | <tex>\ldots </tex>, <br> | + | #:<tex>\ldots </tex>, <br> |
− | <tex>B_{k-2} \rightarrow a_{k-1}a_{k}</tex>. <br> | + | #:<tex>B_{k-2} \rightarrow a_{k-1}a_{k}</tex>. <br> |
− | Удалим из грамматики правило <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>. | + | #Удалим из грамматики правило <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>. |
=== Корректность алгоритма === | === Корректность алгоритма === | ||
{{Теорема | {{Теорема | ||
Строка 33: | Строка 33: | ||
Получим вывод <tex>w</tex> в <tex>\Gamma \cup \Gamma'</tex>, в котором меньше применений правил, отсутствующих в <tex>\Gamma</tex>, чем в исходном. Противоречие. | Получим вывод <tex>w</tex> в <tex>\Gamma \cup \Gamma'</tex>, в котором меньше применений правил, отсутствующих в <tex>\Gamma</tex>, чем в исходном. Противоречие. | ||
}} | }} | ||
+ | |||
== Пример работы == | == Пример работы == | ||
Покажем, как описанный алгоритм будет работать на следующей грамматике: <br> | Покажем, как описанный алгоритм будет работать на следующей грамматике: <br> |
Версия 04:04, 7 ноября 2011
Определение: |
Пусть контекстно-свободная грамматика. Правило называется длинным, если . | —
Постановка задачи
Пусть контекстно-свободная грамматика, содержащая длинные правила. Требуется построить эквивалентную грамматику , не содержащую длинных правил.
Задача удаления длинных правил из грамматики возникает при попытке ее приведения к нормальной форме Хомского.
Алгоритм
С каждым длинным правилом
- Добавим в грамматику
- Добавим в грамматику
новое правило: - Удалим из грамматики правило .
Корректность алгоритма
Теорема: |
Пусть контекстно-свободная грамматика. — грамматика, полученная в результате применения алгоритма к . Тогда — |
Доказательство: |
|
Пример работы
Покажем, как описанный алгоритм будет работать на следующей грамматике:
,
,
.
Для правила
,
,
.
Для правила
,
.
В итоге полученная грамматика
,
,
,
,
,
.