48
правок
Изменения
Нет описания правки
=== Модификация с очередью ===
Заведем несколько структур:
*<tex>\mathtt{is\text{-}epsilonisEpsilon[nonterm_i]}</tex> {{---}} для каждого нетерминала будем хранить пометку, является он <tex>\varepsilon</tex>-порождающим или нет.*<tex>\mathtt{concerned\text{-}rulesconcernedRules[nonterm_i]}</tex> {{---}} для каждого нетерминала будем хранить список номеров тех правил, в правой части которых он встречается;
*<tex>\mathtt{counter[rule_i]}</tex> {{---}} для каждого правила будем хранить счетчик количества нетерминалов в правой части, которые еще не помечены <tex>\varepsilon</tex>-порождающими;
*<tex>\mathtt{Q}</tex> {{---}} очередь нетерминалов, помеченных <tex>\varepsilon</tex>-порождающими, но еще не обработанных.
Сначала проставим <tex>\mathtt{false}</tex> в <tex>\mathtt{is\text{-}epsilonisEpsilon}</tex> для всех нетерминалов, а в <tex>\mathtt{counter}</tex> для каждого правила запишем количество нетерминалов справа от него. Те правила, для которых <tex>\mathtt{counter}</tex> сразу же оказался нулевым, добавим в <tex>\mathtt{Q}</tex> и объявим истинным соответствующий <tex>\mathtt{is\text{-}epsilonisEpsilon}</tex>, так как это <tex>\varepsilon</tex>-правила. Теперь будем доставать из очереди по одному нетерминалу, смотреть на список <tex>\mathtt{concerned\text{-}rulesconcernedRules}</tex> для него и уменьшать <tex>\mathtt{counter}</tex> для всех правил оттуда. Если <tex>\mathtt{counter}</tex> какого-то правила в этот момент обнулился, то нетерминал из левой части этого правила помечается <tex>\varepsilon</tex>-порождающим, если еще не был помечен до этого, и добавляется в <tex>\mathtt{Q}</tex>. Продолжаем, пока очередь не станет пустой.
=== Время работы алгоритма ===
''Поскольку правило 6 содержит справа терминалы, оно заведомо не будет влиять на ответ, поэтому мы не будем его учитывать.''
Построим массив списков <tex>\mathtt{concernedRules}</tex>.
{| class="wikitable"
|-
!<tex>S</tex>
|}
{| class="wikitable"
!<tex>\mathtt{Q}</tex>!colspan=5|<tex>\mathtt{isEpsilon}</tex>!colspan=5 | <tex>\mathtt{counter}</tex>!Комментарий
|-
|rowspan=2|<tex>\text{-}</tex>
!<tex>S</tex>
!<tex>A</tex>
!<tex>B</tex>
!<tex>C</tex>
!<tex>D</tex>
!1
!2
!4
!5
|rowspan=2|Зададим начальные значения массивам <tex>\mathtt{counter}</tex> и <tex>\mathtt{isEpsilon}</tex>.
|-
|0
|0
|0
|0
|0
|3
|2
|2
|0
|-
|rowspan=2|A<br>C
!<tex>S</tex>
!<tex>A</tex>
!<tex>C</tex>
!<tex>D</tex>
!1
!2
!3
!4
!5
|rowspan=2 |Заметим, что правила 3 и 5 являются <tex>\varepsilon</tex>-правилами. Пометим левые нетерминалы из этих правил и добавим их в очередь. После этого в <tex>\mathtt{Q}</tex> лежит <tex>A</tex> и <tex>C</tex>. <tex>\mathtt{counter}</tex> остался без изменений, а <tex>\mathtt{isEpsilon}</tex> выглядит следующим образом:
|-
|0
|1
|0
|1
|0
|3
|2
|0
|2
|0
|-
|rowspan=2|C
!<tex>S</tex>
!<tex>A</tex>
!<tex>C</tex>
!<tex>D</tex>
!1
!2
!3
!4
!5
|rowspan=2|Достанем из очереди <tex>A</tex>, декрементируем те счетчики, которые относятся к связанным с ним правилам. К очереди ничего не добавится, а <tex>\mathtt{counter}</tex> станет таким.
|-
|0
|1
|0
|2
|2
|1
|0
|-
|rowspan=2|B
!<tex>S</tex>
!<tex>A</tex>
!<tex>B</tex>
!<tex>C</tex>
!<tex>D</tex>
!1
!2
!4
!5
|rowspan=2|Достанем из очереди <tex>C</tex>. После проведения действий из алгоритма в очередь добавится <tex>B</tex>.
|-
|0
|1
|1
|1
|0
|1
|2
|0
|0
|-
|rowspan=2|S
!<tex>S</tex>
!<tex>A</tex>
!<tex>C</tex>
!<tex>D</tex>
!1
!2
!4
!5
|rowspan=2|Достанем из очереди <tex>B</tex>. После действий алгоритма в очередь добавится S.
|-
|1
|1
|1
|1
|0
|0
|2
|0
|0
|-
|rowspan=2|<tex>\text{-}</tex>
!<tex>S</tex>
!<tex>A</tex>
!<tex>C</tex>
!<tex>D</tex>
!1
!2
!3
!4
!5
|rowspan=2|Достанем из очереди <tex>S</tex>. Ничего не добавится в очередь и она останется пустой. Алгоритм закончил свое выполнение. Итого в множество <tex>\varepsilon</tex>-правил входят все нетерминалы, кроме <tex>D</tex>.
|-
|1
|1
|0
|}0|-2|Достанем из очереди <tex>S</tex>. Ничего не добавится в очередь и она останется пустой. Алгоритм закончил свое выполнение. Итого в множество <tex>\varepsilon</tex>-правил входят все нетерминалы, кроме <tex>D</tex>.0|0|0
|}
== Источники информации ==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — С. 273: ISBN 5-8459-0261-4 (рус.)
* [http://en.wikipedia.org/wiki/Chomsky_normal_form Wikipedia — Chomsky normal form]
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Нормальные формы КС-грамматик]]
