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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 52 промежуточные версии 14 участников)
Строка 1: Строка 1:
 +
== Порождающие и непорождающие нетерминалы ==
 +
===Описание===
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Символ '''<tex>A</tex>''' называется '''непорождающим''', если из него не может быть выведена конечная терминальная цепочка.
+
[[Формальные_грамматики|Нетерминал]] <tex>A</tex> называется '''порождающим''' (англ. ''generating''), если из него может быть выведена конечная терминальная цепочка. Иначе он называется '''непорождающим'''.
 
}}
 
}}
 +
Очевидно, что если и только если все нетерминалы правой части правила являются порождающими, то порождающим является и нетерминал, стоящий в его левой части.
 +
{{Лемма
 +
|statement=
 +
После удаления из грамматики правил, содержащих непорождающие нетерминалы, язык не изменится.
 +
|proof=
 +
Непорождающие нетерминалы по определению не могли участвовать в выводе какого-либо слова.
 +
}}
 +
 +
===Алгоритм===
 +
'''Шаг 0'''. Множество порождающих нетерминалов пустое.<br>
 +
'''Шаг 1'''. Находим правила, не содержащие нетерминалов в правых частях и добавляем нетерминалы, встречающихся в левых частях таких правил, в множество.<br>
 +
'''Шаг 2'''. Если найдено такое правило, что все нетерминалы, стоящие в его правой части, уже входят в множество, то добавим в множество нетерминалы, стоящие в его левой части. <br>
 +
'''Шаг 3'''. Повторим предыдущий шаг, если множество порождающих нетерминалов изменилось.<br>
 +
В результате получаем множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.
  
Рассматривая правила грамматики,  можно сделать  вывод,  что если и только если все нетерминальные символы правой части являются порождающими, то порождающим является и символ, стоящий в левой части. Последнее утверждение позволяет написать процедуру обнаружения непорождающих символов в следующем виде:
+
=== Время работы алгоритма ===
# Составить список нетерминалов, для которых найдется хотя  бы одно правило, правая часть которого не содержит нетерминалов.  
+
Данный алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</tex>, где <tex>\left| \Gamma \right|</tex> {{---}} размер грамматики. Однако используя [[Очередь|очередь]] можно ускорить его до <tex>O(\left| \Gamma \right|)</tex>.
# Если найдено такое правило,  что все нетерминалы, стоящие  в его правой части уже занесены в список,  то добавить  в  список  нетерминал, стоящий в его левой части.
 
# Если на шаге 2 список больше не пополняется,  то  получен  список всех порождающих нетерминалов грамматики,  а все нетерминалы, не попавшие в него, являются непорождающими.
 
  
 +
===Модификация алгоритма с очередью===
 +
Для реализации алгоритма поиска непорождающих нетерминалов будем использовать следующие структуры:
 +
*<tex>\mathrm{isGenerating[nonterm_i]}</tex> {{---}} является ли нетерминал <tex>\mathrm{nonterm_i}</tex> порождающим или нет,
 +
*<tex>\mathrm{counter[rule_i]}</tex> {{---}} счетчик количества нетерминалов, которые ещё не помечены порождающими, для каждого из правил,
 +
*<tex>\mathrm{concernedRules[nonterm_i]}</tex> {{---}} для каждого нетерминала <tex>\mathrm{nonterm_i}</tex> список номеров правил, в правой части которых он встречается,
 +
*<tex>\mathrm{Q}</tex> {{---}} очередь нетерминалов, помеченных порождающими, но ещё не обработанных.
 +
 +
Вначале для всех нетерминалов в <tex>\mathrm{isGenerating}</tex> поставим <tex>false</tex>. В <tex>\mathrm{counter}</tex> поставим количество нетерминалов в правой части. Нетерминалы, у которых счётчик <tex>\mathrm{counter}</tex> нулевой, добавим в очередь и отметим их порождающими.<br>
 +
Пока в очереди есть элементы, достаём очередной нетерминал и уменьшаем <tex>\mathrm{counter}</tex> для всех правил из <tex>\mathrm{concernedRules}</tex> для данного нетерминала. Если счётчик количества порождающих терминалов обнулился, то добавим нетерминал, стоящий в левой части данного правила в очередь и пометим его порождающим.<br>
 +
Каждый из нетерминалов попадёт в очередь только один раз, следовательно мы пройдем по списку правил, в правой части которых он встречается, один раз. Таким образом, суммарно получаем <tex>O(\left| \Gamma \right|)</tex>.
 +
 +
=== Пример ===
 +
Рассмотрим следующую грамматику: <br>
 +
 +
:<tex>
 +
S\rightarrow Ac\\
 +
A\rightarrow SD\\
 +
D\rightarrow aD\\
 +
A\rightarrow a   
 +
</tex>
 +
Применяя описанный алгоритм:
 +
# Изначально множество порождающих нетерминалов состоит из одного элемента <tex>A</tex>.
 +
# Добавим в множество нетерминал <tex>S</tex>, так как существует правило <tex>S\rightarrow Ac</tex>, в правой части которого стоят нетерминал <tex>A</tex>, который есть в множестве, и терминал <tex>c</tex>.
 +
# После следующего обхода правил из грамматики множество не изменится.
 +
# Теперь удалим правила <tex>A\rightarrow SD</tex> и <tex>D\rightarrow aD</tex>, так как они содержат нетерминалы, которых нет в полученном множестве.
 +
 +
== Достижимые и недостижимые нетерминалы ==
 +
===Описание===
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Символ '''<tex>A</tex>''' называется '''недостижимым''' в КС-грамматике '''<tex>\Gamma</tex>''', если строку, содержащую '''<tex>A</tex>''', нельзя вывести из стартового нетерминала.
+
Нетерминал <tex>A</tex> называется '''достижимым''' (англ. ''reachable'') в [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|КС-грамматике]] <tex>\Gamma</tex>, если существует порождение <tex>S \Rightarrow^* \alpha A \beta</tex>. Иначе он называется '''недостижимым''' (англ. ''unreachable'').
 +
}}
 +
Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми.
 +
{{Лемма
 +
|statement=
 +
После удаления из грамматики правил, содержащих недостижимые нетерминалы, язык не изменится.
 +
|proof=
 +
Недостижимые нетерминалы по определению не достижимы из стартового, следовательно они не могли участвовать в выводе какого-либо слова.
 
}}
 
}}
 +
===Алгоритм===
 +
'''Шаг 0.''' Множество достижимых нетерминалов состоит из единственного элемента: <tex>\lbrace S \rbrace</tex>.<br>
 +
'''Шаг 1.''' Если найдено правило, в левой части которого стоит нетерминал, содержащийся в множестве, добавим в множество все нетерминалы из правой части.<br>
 +
'''Шаг 2.''' Повторим предыдущий шаг, если множество порождающих нетерминалов изменилось.<br>
 +
Получаем множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми.
 +
 +
=== Время работы алгоритма ===
 +
Данный алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</tex>, однако используя [[Обход_в_глубину,_цвета_вершин|обход в глубину]] можно ускорить его до <tex>O(\left| \Gamma \right|)</tex>.
  
Рассматривая правила грамматики, можно заметить , что если нетерминал в левой части правила является достижимым , то и все символы правой части являются достижимыми. Это свойство правил является основой процедуры выявления недостижимых символов, которую можно записать так:  
+
=== Пример ===
# Образовать одноэлементный список, состоящий из начального символа
+
Рассмотрим следующую грамматику:<br>
# Если найдено правило, левая часть которого уже имеется в списке, то включить в  список все символы, содержащиеся в его правой части.
 
# Если на шаге 2 новые нетерминалы в список больше  не  добавляются,  то получен список всех достижимых нетерминалов, а нетерминалы, не попавшие в список, являются недостижимыми.
 
  
 +
:<tex>
 +
    S\rightarrow AB|CD\\
 +
    A\rightarrow EF\\
 +
    G\rightarrow AD\\
 +
    C\rightarrow c
 +
</tex>
 +
Применяя описанный алгоритм:
 +
# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \rbrace</tex>.
 +
# Из <tex>S</tex> достижимы нетерминалы <tex>A</tex>, <tex>B</tex>, <tex>C</tex> и <tex>D</tex>. Добавим их в множество и получим  <tex>\lbrace S, A, B, C, D \rbrace</tex>.
 +
# Множество изменилось. Переберём заново правила из грамматики. Из <tex>A</tex> можно вывести <tex>E</tex> и <tex>F</tex>, добавим их в множество.
 +
# Снова переберём правила. Из <tex>C</tex> можно вывести только терминал, а <tex>G</tex> нет в множестве.
 +
# После последнего обхода правил грамматики множество не изменилось, значит мы нашли все достижимые нетерминалы: <tex>\lbrace S, A, B, C, D, E, F \rbrace</tex>.
 +
# Теперь удалим правило <tex>G\rightarrow AD</tex>, так как оно содержит в левой части нетерминал, которого нет в полученном множестве.
 +
 +
== Полезные и бесполезные нетерминалы ==
 +
===Описание===
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Символ '''<tex>A</tex>''' называется '''бесполезным''' в
+
Нетерминал <tex>A</tex> называется '''полезным''' (англ. ''useful'') в КС-грамматике <tex>\Gamma</tex>, если он может участвовать в выводе, то есть существует порождение вида <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* w</tex>. Иначе он называется '''бесполезным''' (англ. ''useless'').
КС-грамматике '''<tex>\Gamma</tex>''', если он не может встретиться в выводе слова из терминалов. То есть не существует порождения вида <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* w</tex>, где <tex>w</tex> {{---}} строка терминалов.
 
 
}}
 
}}
 +
 
{{Теорема
 
{{Теорема
 
|id=th1
 
|id=th1
 
|statement=
 
|statement=
Грамматика <tex>\Gamma</tex> не содержит бесполезных символов '''тогда и только тогда, когда''' она не содержит ни недостижимых символов, ни непорождающих.
+
Грамматика <tex>\Gamma</tex> не содержит бесполезных нетерминалов тогда и только тогда, когда грамматика <tex>\Gamma</tex> не содержит ни недостижимых нетерминалов, ни непорождающих.
 
|proof=
 
|proof=
<tex>\Rightarrow</tex> Очевидно, т.к. недостижимые и непорождающие символы являются бесполезными.
+
<tex>\Leftarrow</tex>
<tex>\Leftarrow</tex> Рассмотрим любой нетерминал <tex>A</tex>. Так как он достижимый, существуют <tex>\alpha</tex> и <tex>\beta</tex>, такие, что <tex>S \Rightarrow ^* \alpha A \beta</tex>. Из того, что любой сивол является порождающим, следует, что из любой строки можно вывести строку из терминалов. Значит, существует <tex>\omega \in \Sigma ^ *</tex>: <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* \omega</tex>, и <tex>A</tex> - не бесполезный.
+
<br/>
 +
:Очевидно, так как недостижимые и непорождающие нетерминалы являются бесполезными.
 +
 
 +
<tex>\Rightarrow</tex>
 +
<br/>
 +
:Рассмотрим любой нетерминал <tex>A</tex>. Так как он достижим, существуют <tex>\alpha</tex> и <tex>\beta</tex> такие, что <tex>S \Rightarrow ^* \alpha A \beta</tex>. Из того, что любой нетерминал является порождающим, следует, что из любой строки можно вывести строку из терминалов. Значит, существует <tex>\omega \in \Sigma ^ *</tex>: <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* \omega</tex>, и <tex>A</tex> {{---}} не бесполезный.
 
}}
 
}}
  
 +
===Алгоритм===
 +
Алгоритм состоит из двух этапов:
 +
# Удалить из грамматики правила, содержащие непорождающие нетерминалы.
 +
# Удалить из грамматики правила, содержащие недостижимые нетерминалы.
 +
 +
=== Корректность алгоритма ===
 +
Достаточность данных действий следует из доказанной выше теоремы.
  
 
{{Теорема
 
{{Теорема
|id=th2
+
|id=th1
 
|statement=
 
|statement=
Пусть <tex>G</tex> {{---}} КС-грамматика, и <tex>L(G)\ne\varnothing</tex>. Пусть <tex>G_1</tex> - грамматика, полученная с помощью следующих двух шагов:
+
После удаления из грамматики правил, содержащих недостижимые нетерминалы, не появятся новые непорождающие нетерминалы.
 +
|proof=
 +
Допустим, что в грамматике появился непорождающий нетерминал <tex>A</tex>. Так как до удаления недостижимых нетерминалов существовал вывод из <tex>A</tex> некоторой конечной цепочки терминалов <tex>\omega</tex>, то было удалено хотя бы какое-то одно правило из этого вывода.
  
1) Удаляются непорождающие символы и все продукции, содержащие один или несколько таких символов. Пусть <tex>G_2</tex> {{---}} полученная в результате грамматика.
+
Пусть <tex>B\rightarrow\alpha</tex> {{---}} правило, первым из удалённых применяемое в выводе <tex>A \Rightarrow ^* \omega</tex>. Оно могло быть удалено только в том случае, если в <tex>\alpha</tex> присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то <tex>B</tex> — достижим, следовательно достижимы и все нетерминалы из <tex>\alpha</tex>. Значит, это правило не могло быть удалено.
 +
}}
  
2) Удаляются все символы, недостижимые из <tex>G_2</tex>.
+
=== Пример ===
  
Тогда <tex>G_1</tex> не имеет бесполезных символов и <tex>L(G_1)=L(G)</tex>.
+
1. Пусть нам дана грамматика: <br>
|proof=
 
Пусть <tex>X</tex> {{---}} оставшийся символ. Известно, что <tex>X\Rightarrow _G^* w</tex> для некоторой цепочки <tex>w</tex> из терминалов. Кроме того, каждый символ, использованный в этом порождении, достижим, поэтому <tex>S\Rightarrow _{G_2}^* w</tex>.
 
  
Поскольку <tex>X</tex> не был удален на втором шаге, известно, что существует такие <tex>\alpha</tex> и <tex>\beta</tex>, для которых <tex>S\Rightarrow _{G_2}^* \alpha X\beta</tex>. Кроме того, каждый символ, использованный в этом порождении, достижим, поэтому <tex>S\Rightarrow _{G_1}^* \alpha X\beta</tex>.
+
:<tex>
 +
    S\rightarrow AS|BS|s \\
 +
    E\rightarrow EF|FF \\
 +
    A\rightarrow a \\
 +
    F\rightarrow f
 +
</tex><br>
 +
2. Удалим правила, содержащие непорождающие нетерминалы: <br>
  
Также известно, что каждый символ в цепочке <tex>\alpha X\beta</tex> достижим, поэтому каждый из них является порождающим в <tex>G_2</tex>. Порождение некоторой терминальной цепочки, например, <tex>\alpha X\beta\Rightarrow _{G_2}^* xwy</tex>, содержит только символы, достижимые из <tex>S</tex>, поскольку они достижимы из символов в цепочке <tex>\alpha X\beta</tex>. Таким образом, это порождение есть также порождение в <tex>G_1</tex>, то есть <tex>S\Rightarrow _{G_1}^* \alpha X\beta\Rightarrow _{G_1}^* xwy</tex>.
+
:<tex>
 +
    S\rightarrow AS|s \\
 +
    E\rightarrow EF|FF \\
 +
    A\rightarrow a \\
 +
    F\rightarrow f
 +
</tex><br>
 +
3. Теперь удалим недостижимые нетерминалы:<br>
  
Итак, <tex>X</tex> полезен в <tex>G_1</tex>. Ввиду произвольности <tex>X</tex> в <tex>G_1</tex> можно заключить, что <tex>G_1</tex> не имеет бесполезных символов.
+
:<tex>
 
+
    S\rightarrow AS|s \\  
<tex>L(G_1)\subseteq L(G)</tex>, так как при построении <tex>G_1</tex> из <tex>G</tex> символы и продукции только убирались. Докажем, что <tex>L(G_1)\supseteq L(G)</tex>. Если <tex>w\in L(G)</tex>, то <tex>S\Rightarrow _{G}^* w</tex>. Каждый символ в этом порождении является как достижимым, так и порождающим, поэтому порождение в <tex>G_1</tex> его также содержит. Таким образом, <tex>S\Rightarrow _{G_1}^* w</tex>, <tex>w\in L(G_1)</tex> и <tex>L(G)=L(G_1)</tex>.
+
    A\rightarrow a
}}
+
</tex>
  
''Примечание:''
+
=== Замечание ===
 +
Шаги алгоритма нельзя менять местами.
  
Эти шаги нельзя менять местами. Рассмотрим следующую грамматику:
+
Рассмотрим следующую грамматику: <br>
  
<tex>S\rightarrow AB|a</tex>
+
:<tex>
 +
    S\rightarrow AB|a \\
 +
    A\rightarrow b
 +
</tex>
  
<tex>A\rightarrow b</tex>
+
Все нетерминалы в этой грамматике достижимы. Однако, если удалить <tex>B</tex> как непорождающий, то нетерминал <tex>A</tex> станет недостижимым.
 +
== См. также  ==
 +
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
 +
* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]
  
Если начать с проверки достижимости, то все символы грамматики оказываются достижимыми. Если затем удалить <tex>B</tex> как непорождающий символ, то останется грамматика с бесполезными символами <tex>A</tex> и <tex>b</tex>.
+
== Источники информации ==
 +
* [[wikipedia:Formal_grammar | Wikipedia {{---}} Formal grammar]]
 +
* [http://en.wikipedia.org/wiki/Chomsky_normal_form Wikipedia {{---}} Chomsky normal form]
 +
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
  
== Литература ==
+
[[Категория: Теория формальных языков]]
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
+
[[Категория: Контекстно-свободные грамматики]]
 +
[[Категория: Нормальные формы КС-грамматик]]

Текущая версия на 19:21, 4 сентября 2022

Порождающие и непорождающие нетерминалы

Описание

Определение:
Нетерминал [math]A[/math] называется порождающим (англ. generating), если из него может быть выведена конечная терминальная цепочка. Иначе он называется непорождающим.

Очевидно, что если и только если все нетерминалы правой части правила являются порождающими, то порождающим является и нетерминал, стоящий в его левой части.

Лемма:
После удаления из грамматики правил, содержащих непорождающие нетерминалы, язык не изменится.
Доказательство:
[math]\triangleright[/math]
Непорождающие нетерминалы по определению не могли участвовать в выводе какого-либо слова.
[math]\triangleleft[/math]

Алгоритм

Шаг 0. Множество порождающих нетерминалов пустое.
Шаг 1. Находим правила, не содержащие нетерминалов в правых частях и добавляем нетерминалы, встречающихся в левых частях таких правил, в множество.
Шаг 2. Если найдено такое правило, что все нетерминалы, стоящие в его правой части, уже входят в множество, то добавим в множество нетерминалы, стоящие в его левой части.
Шаг 3. Повторим предыдущий шаг, если множество порождающих нетерминалов изменилось.
В результате получаем множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.

Время работы алгоритма

Данный алгоритм работает за [math]O(\left| \Gamma \right| ^ 2)[/math], где [math]\left| \Gamma \right|[/math] — размер грамматики. Однако используя очередь можно ускорить его до [math]O(\left| \Gamma \right|)[/math].

Модификация алгоритма с очередью

Для реализации алгоритма поиска непорождающих нетерминалов будем использовать следующие структуры:

  • [math]\mathrm{isGenerating[nonterm_i]}[/math] — является ли нетерминал [math]\mathrm{nonterm_i}[/math] порождающим или нет,
  • [math]\mathrm{counter[rule_i]}[/math] — счетчик количества нетерминалов, которые ещё не помечены порождающими, для каждого из правил,
  • [math]\mathrm{concernedRules[nonterm_i]}[/math] — для каждого нетерминала [math]\mathrm{nonterm_i}[/math] список номеров правил, в правой части которых он встречается,
  • [math]\mathrm{Q}[/math] — очередь нетерминалов, помеченных порождающими, но ещё не обработанных.

Вначале для всех нетерминалов в [math]\mathrm{isGenerating}[/math] поставим [math]false[/math]. В [math]\mathrm{counter}[/math] поставим количество нетерминалов в правой части. Нетерминалы, у которых счётчик [math]\mathrm{counter}[/math] нулевой, добавим в очередь и отметим их порождающими.
Пока в очереди есть элементы, достаём очередной нетерминал и уменьшаем [math]\mathrm{counter}[/math] для всех правил из [math]\mathrm{concernedRules}[/math] для данного нетерминала. Если счётчик количества порождающих терминалов обнулился, то добавим нетерминал, стоящий в левой части данного правила в очередь и пометим его порождающим.
Каждый из нетерминалов попадёт в очередь только один раз, следовательно мы пройдем по списку правил, в правой части которых он встречается, один раз. Таким образом, суммарно получаем [math]O(\left| \Gamma \right|)[/math].

Пример

Рассмотрим следующую грамматику:

[math] S\rightarrow Ac\\ A\rightarrow SD\\ D\rightarrow aD\\ A\rightarrow a [/math]

Применяя описанный алгоритм:

  1. Изначально множество порождающих нетерминалов состоит из одного элемента [math]A[/math].
  2. Добавим в множество нетерминал [math]S[/math], так как существует правило [math]S\rightarrow Ac[/math], в правой части которого стоят нетерминал [math]A[/math], который есть в множестве, и терминал [math]c[/math].
  3. После следующего обхода правил из грамматики множество не изменится.
  4. Теперь удалим правила [math]A\rightarrow SD[/math] и [math]D\rightarrow aD[/math], так как они содержат нетерминалы, которых нет в полученном множестве.

Достижимые и недостижимые нетерминалы

Описание

Определение:
Нетерминал [math]A[/math] называется достижимым (англ. reachable) в КС-грамматике [math]\Gamma[/math], если существует порождение [math]S \Rightarrow^* \alpha A \beta[/math]. Иначе он называется недостижимым (англ. unreachable).

Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми.

Лемма:
После удаления из грамматики правил, содержащих недостижимые нетерминалы, язык не изменится.
Доказательство:
[math]\triangleright[/math]
Недостижимые нетерминалы по определению не достижимы из стартового, следовательно они не могли участвовать в выводе какого-либо слова.
[math]\triangleleft[/math]

Алгоритм

Шаг 0. Множество достижимых нетерминалов состоит из единственного элемента: [math]\lbrace S \rbrace[/math].
Шаг 1. Если найдено правило, в левой части которого стоит нетерминал, содержащийся в множестве, добавим в множество все нетерминалы из правой части.
Шаг 2. Повторим предыдущий шаг, если множество порождающих нетерминалов изменилось.
Получаем множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми.

Время работы алгоритма

Данный алгоритм работает за [math]O(\left| \Gamma \right| ^ 2)[/math], однако используя обход в глубину можно ускорить его до [math]O(\left| \Gamma \right|)[/math].

Пример

Рассмотрим следующую грамматику:

[math] S\rightarrow AB|CD\\ A\rightarrow EF\\ G\rightarrow AD\\ C\rightarrow c [/math]

Применяя описанный алгоритм:

  1. Возьмём множество, состоящее из единственного элемента: [math]\lbrace S \rbrace[/math].
  2. Из [math]S[/math] достижимы нетерминалы [math]A[/math], [math]B[/math], [math]C[/math] и [math]D[/math]. Добавим их в множество и получим [math]\lbrace S, A, B, C, D \rbrace[/math].
  3. Множество изменилось. Переберём заново правила из грамматики. Из [math]A[/math] можно вывести [math]E[/math] и [math]F[/math], добавим их в множество.
  4. Снова переберём правила. Из [math]C[/math] можно вывести только терминал, а [math]G[/math] нет в множестве.
  5. После последнего обхода правил грамматики множество не изменилось, значит мы нашли все достижимые нетерминалы: [math]\lbrace S, A, B, C, D, E, F \rbrace[/math].
  6. Теперь удалим правило [math]G\rightarrow AD[/math], так как оно содержит в левой части нетерминал, которого нет в полученном множестве.

Полезные и бесполезные нетерминалы

Описание

Определение:
Нетерминал [math]A[/math] называется полезным (англ. useful) в КС-грамматике [math]\Gamma[/math], если он может участвовать в выводе, то есть существует порождение вида [math]S \Rightarrow ^* \alpha A \beta \Rightarrow ^* w[/math]. Иначе он называется бесполезным (англ. useless).


Теорема:
Грамматика [math]\Gamma[/math] не содержит бесполезных нетерминалов тогда и только тогда, когда грамматика [math]\Gamma[/math] не содержит ни недостижимых нетерминалов, ни непорождающих.
Доказательство:
[math]\triangleright[/math]

[math]\Leftarrow[/math]

Очевидно, так как недостижимые и непорождающие нетерминалы являются бесполезными.

[math]\Rightarrow[/math]

Рассмотрим любой нетерминал [math]A[/math]. Так как он достижим, существуют [math]\alpha[/math] и [math]\beta[/math] такие, что [math]S \Rightarrow ^* \alpha A \beta[/math]. Из того, что любой нетерминал является порождающим, следует, что из любой строки можно вывести строку из терминалов. Значит, существует [math]\omega \in \Sigma ^ *[/math]: [math]S \Rightarrow ^* \alpha A \beta \Rightarrow ^* \omega[/math], и [math]A[/math] — не бесполезный.
[math]\triangleleft[/math]

Алгоритм

Алгоритм состоит из двух этапов:

  1. Удалить из грамматики правила, содержащие непорождающие нетерминалы.
  2. Удалить из грамматики правила, содержащие недостижимые нетерминалы.

Корректность алгоритма

Достаточность данных действий следует из доказанной выше теоремы.

Теорема:
После удаления из грамматики правил, содержащих недостижимые нетерминалы, не появятся новые непорождающие нетерминалы.
Доказательство:
[math]\triangleright[/math]

Допустим, что в грамматике появился непорождающий нетерминал [math]A[/math]. Так как до удаления недостижимых нетерминалов существовал вывод из [math]A[/math] некоторой конечной цепочки терминалов [math]\omega[/math], то было удалено хотя бы какое-то одно правило из этого вывода.

Пусть [math]B\rightarrow\alpha[/math] — правило, первым из удалённых применяемое в выводе [math]A \Rightarrow ^* \omega[/math]. Оно могло быть удалено только в том случае, если в [math]\alpha[/math] присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то [math]B[/math] — достижим, следовательно достижимы и все нетерминалы из [math]\alpha[/math]. Значит, это правило не могло быть удалено.
[math]\triangleleft[/math]

Пример

1. Пусть нам дана грамматика:

[math] S\rightarrow AS|BS|s \\ E\rightarrow EF|FF \\ A\rightarrow a \\ F\rightarrow f [/math]

2. Удалим правила, содержащие непорождающие нетерминалы:

[math] S\rightarrow AS|s \\ E\rightarrow EF|FF \\ A\rightarrow a \\ F\rightarrow f [/math]

3. Теперь удалим недостижимые нетерминалы:

[math] S\rightarrow AS|s \\ A\rightarrow a [/math]

Замечание

Шаги алгоритма нельзя менять местами.

Рассмотрим следующую грамматику:

[math] S\rightarrow AB|a \\ A\rightarrow b [/math]

Все нетерминалы в этой грамматике достижимы. Однако, если удалить [math]B[/math] как непорождающий, то нетерминал [math]A[/math] станет недостижимым.

См. также

Источники информации

  • Wikipedia — Formal grammar
  • Wikipedia — Chomsky normal form
  • Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)