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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 18: Строка 18:
 
<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>\Gamma</tex>
+
Удалим из грамматики правило <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>. Проделаем описанную операцию с каждым длинным правилом в <tex>\Gamma</tex>.
  
 
== Пример работы ==
 
== Пример работы ==

Версия 23:35, 26 октября 2011

Задача удаления длинных правил из грамматики возникает при попытке ее приведения к нормальной форме Хомского.


Определение:
Пусть [math]\Gamma[/math]контекстно-свободная грамматика. Правило [math]A \rightarrow \beta [/math] называется длинным если [math]|\beta| \gt 2[/math]


Постановка задачи

Пусть [math]\Gamma[/math]контекстно-свободная грамматика, содержащая длинные правила. Требуется построить эквивалентную грамматику [math]\Gamma'[/math], не содержащую длинных правил.

Алгоритм

Расмотрим длинное правило [math]A \rightarrow a_1 a_2 \ldots a_k[/math], [math]k \gt 2[/math], [math]a_i \in \Sigma \cup N[/math]
Добавим в грамматику [math]k - 2[/math] новых нетерминалов [math]B_1, B_2, \ldots B_{k-2}[/math]
Добавим в грамматику [math]k-1[/math] новое правило:
[math]A \rightarrow a_1B_1[/math]
[math]B_1 \rightarrow a_2B_2[/math]
[math]B_2 \rightarrow a_3B_3[/math]
[math]\ldots [/math]
[math]B_{k-2} \rightarrow a_{k-1}a_{k}[/math]
Удалим из грамматики правило [math]A \rightarrow a_1 a_2 \ldots a_k[/math]. Проделаем описанную операцию с каждым длинным правилом в [math]\Gamma[/math].

Пример работы

Покажем, как описанный алгоритм будет работать на следующей грамматике:
[math]S \rightarrow AB[/math]
[math]A \rightarrow aBcB[/math]
[math]B \rightarrow def[/math]

Для правила [math]A \rightarrow aBcB[/math] вводим 2 новых нетерминала [math]A_1, A_2[/math], и 3 новых правила:
[math]A \rightarrow aA_1[/math]
[math]A_1 \rightarrow BA_2[/math]
[math]A_2 \rightarrow bB[/math]

Для правила [math]B \rightarrow def[/math] вводим 1 новыq нетерминал [math]B_1[/math], и 2 новых правила:
[math]B \rightarrow dB_1[/math]
[math]B_1 \rightarrow ef[/math]

В итоге, полученная грамматика [math]\Gamma'[/math] будет иметь вид:
[math]S \rightarrow AB[/math]
[math]A \rightarrow aA_1[/math]
[math]A_1 \rightarrow BA_2[/math]
[math]A_2 \rightarrow bB[/math]
[math]B \rightarrow dB_1[/math]
[math]B_1 \rightarrow ef[/math]