Материал из Викиконспекты
Несколько определений
| Определение: |
| Грамматикой в нормальной форме Хомского (Chomsky normal form) называется контекстно-свободная грамматика, в которой могут содержатся правила только следующего вида:
[math]A \rightarrow B C [/math],
[math]A \rightarrow a [/math],
[math]S \rightarrow \varepsilon [/math],
где [math] a [/math] — терминал, [math] A, B, C [/math] — нетерминалы, [math] S [/math] — стартовая вершина, [math] \varepsilon [/math] — пустая строка, стартовая вершина не содержится в правых частях правил. |
| Определение: |
| Пара нетерминалов [math] A [/math] и [math] B [/math] называется узловой, если [math] A \Rightarrow^* B [/math].
[math] \forall A [/math] выполняется [math] (A, A) [/math] — узловая пара.
Если [math] (A, B) [/math] — узловая пара, а [math] B \rightarrow C [/math], то [math] (A, C) [/math] тоже узловая пара. |
Приведение грамматики к нормальной форме Хомского
| Теорема: |
Любую контекстно-свободную грамматику можно привести к нормальной форме Хомского. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Рассмотрим контекстно-свободную грамматику [math] \Gamma [/math]. Для приведения ее к нормальной форме Хомского необходимо выполнить три шага. На каждом шаге мы строим новую [math] \Gamma_i [/math], которая допускает тот же язык, что и [math] \Gamma [/math].
- Удаление [math] \varepsilon [/math]-правил.
- Воспользуемся алгоритмом удаления [math] \varepsilon [/math]-правил из грамматики. Получим [math] \Gamma_1 [/math].
- Преобразование узловых пар.
- Для каждой узловой пары [math] (A, B) [/math], найдем все правила [math] B \rightarrow w [/math], где [math] w [/math] — произвольная строка терминалов и нетерминалов, и добавим [math] A \rightarrow w [/math] в [math] \Gamma_2 [/math].
- Преобразование длинных правил.
- Воспользуемся алгоритмом удаления длинных правил из грамматики. Получим [math] \Gamma_3 [/math].
Таким образом мы получили грамматику [math] \Gamma_3 [/math] в нормальной форме Хомского, которая допускает тот же язык, что и [math] \Gamma [/math]. |
| [math]\triangleleft[/math] |
Литература
