Удаление цепных правил из грамматики — различия между версиями
(→Алгоритм) |
(→Пример) |
||
Строка 55: | Строка 55: | ||
# Повторим второй пункт для правила <tex>B\rightarrow C</tex> и пары <tex>(A, B)</tex>, и получем множество <tex>\lbrace (A, A), (A, B), (A, C), (B, B), (B, C) \rbrace</tex>. | # Повторим второй пункт для правила <tex>B\rightarrow C</tex> и пары <tex>(A, B)</tex>, и получем множество <tex>\lbrace (A, A), (A, B), (A, C), (B, B), (B, C) \rbrace</tex>. | ||
# Для каждой пары добавим в <tex>\Gamma'</tex> новые правила: | # Для каждой пары добавим в <tex>\Gamma'</tex> новые правила: | ||
− | |||
#* <tex>A\rightarrow b</tex> для <tex>(A, B)</tex> | #* <tex>A\rightarrow b</tex> для <tex>(A, B)</tex> | ||
#* <tex>A\rightarrow c</tex> и <tex>A\rightarrow DD</tex> для <tex>(A, C)</tex> | #* <tex>A\rightarrow c</tex> и <tex>A\rightarrow DD</tex> для <tex>(A, C)</tex> | ||
− | |||
#* <tex>B\rightarrow c</tex> и <tex>B\rightarrow DD</tex> для <tex>(B, C)</tex> | #* <tex>B\rightarrow c</tex> и <tex>B\rightarrow DD</tex> для <tex>(B, C)</tex> | ||
− | #* <tex> | + | #* Пары <tex>(A, A)</tex> и <tex>(B, B)</tex> новых правил не добавят. |
==Литература== | ==Литература== |
Версия 21:43, 30 октября 2013
Определение: |
Цепное правило — правило вида | , где и — нетерминалы.
Постановка задачи
Пусть контекстно-свободная грамматика, содержащая цепные правила. Требуется построить эквивалентную грамматику , не содержащую цепных правил.
Задача удаления цепных правил из грамматики возникает при попытке её приведения к нормальной форме Хомского.
Алгоритм
Определение: |
Цепная пара — упорядоченная пара | , в которой , используя только цепные правила.
Алгоритм удаления цепных правил из грамматики:
- Найти все цепные пары в грамматике .
- Для каждой цепной пары добавить в грамматику все правила вида , где — нецепное правило из .
- Удалить все цепные правила
Найти все цепные пары можно по индукции:
Базис.
— цепная пара для любого нетерминала, так как за ноль шагов.Индукция. Если пара
— цепная, и есть правило , то — цепная пара.Нетрудно понять, что такой алгоритм найдет все цепные правила грамматики
, и только их.Корректность алгоритма
Теорема: |
Пусть контекстно-свободная грамматика. — грамматика, полученная в результате применения алгоритма к . Тогда — |
Доказательство: |
|
Пример
Рассмотрим грамматику:
- В этой грамматике два цепных правила
Теперь множество цепных пар будет состоять из и .
и . Для каждого такого правила создадим цепную пару. - Рассмотрим цепное правило
добавим в множество пару , у которой первый элемент такой же как у найденной, а второй равен правому нетерминалу из текущего правила.
. Так как существует цепная пара , второй элемент которой совпадает с левым нетерминалом из правила, - Повторим второй пункт для правила и пары . Теперь множество цепных пар будет состоять из , , и .
- Повторим второй пункт для правила и пары , и получем множество .
- Для каждой пары добавим в
- для
- и для
- и для
- Пары и новых правил не добавят.
новые правила:
Литература
- Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)