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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Достижимые и недостижимые нетерминалы)
м (rollbackEdits.php mass rollback)
 
(не показано 28 промежуточных версий 7 участников)
Строка 1: Строка 1:
 
== Порождающие и непорождающие нетерминалы ==
 
== Порождающие и непорождающие нетерминалы ==
 +
===Описание===
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Нетерминал <tex>A</tex> называется '''порождающим''', если из него может быть выведена конечная терминальная цепочка. Иначе он называется '''непорождающим'''.
+
[[Формальные_грамматики|Нетерминал]] <tex>A</tex> называется '''порождающим''' (англ. ''generating''), если из него может быть выведена конечная терминальная цепочка. Иначе он называется '''непорождающим'''.
 
}}
 
}}
 
+
Очевидно, что если и только если все нетерминалы правой части правила являются порождающими, то порождающим является и нетерминал, стоящий в его левой части.  
Очевидно, что если и только если все нетерминалы правой части являются порождающими, то порождающим является и нетерминал, стоящий в левой части. Это позволяет обнаружить непорождающие нетерминалы с помощью следующей процедуры.
 
# Найти правила, не содержащие нетерминалов в правых частях. Составить множество нетерминалов, встречающихся в левых частях таких правил.
 
# Если найдено такое правило, что все нетерминалы, стоящие в его правой части, уже входят в множество, то добавить в множество нетерминалы, стоящие в его левой части.
 
# Если на шаге 2 множество изменилось, повторить шаг 2.
 
# Получено множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.
 
 
 
 
 
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Строка 19: Строка 13:
 
}}
 
}}
  
 +
===Алгоритм===
 +
'''Шаг 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>.
 +
 +
===Модификация алгоритма с очередью===
 +
Для реализации алгоритма поиска непорождающих нетерминалов будем использовать следующие структуры:
 +
*<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>S \Rightarrow^* \alpha A \beta</tex>. Иначе он называется '''недостижимым'''.
+
Нетерминал <tex>A</tex> называется '''достижимым''' (англ. ''reachable'') в [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|КС-грамматике]] <tex>\Gamma</tex>, если существует порождение <tex>S \Rightarrow^* \alpha A \beta</tex>. Иначе он называется '''недостижимым''' (англ. ''unreachable'').
 
}}
 
}}
 
+
Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми.  
Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми. Найти недостижимые нетерминалы можно с помощью следующей процедуры.
 
# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \rbrace</tex>.
 
# Если найдено правило, в левой части которого стоит нетерминал, содержащийся в множестве, добавить в множество все нетерминалы из правой части.
 
# Если на шаге 2 множество изменилось, повторить шаг 2.
 
# Получено множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми.
 
 
 
 
 
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Строка 39: Строка 62:
 
Недостижимые нетерминалы по определению не достижимы из стартового, следовательно они не могли участвовать в выводе какого-либо слова.
 
Недостижимые нетерминалы по определению не достижимы из стартового, следовательно они не могли участвовать в выводе какого-либо слова.
 
}}
 
}}
 +
===Алгоритм===
 +
'''Шаг 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>
<tex>
+
 
\begin{array}{l l} 
+
:<tex>
 
     S\rightarrow AB|CD\\
 
     S\rightarrow AB|CD\\
 
     A\rightarrow EF\\
 
     A\rightarrow EF\\
 
     G\rightarrow AD\\
 
     G\rightarrow AD\\
 
     C\rightarrow c
 
     C\rightarrow c
 
\end{array}
 
 
</tex>
 
</tex>
 +
Применяя описанный алгоритм:
 
# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \rbrace</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>S</tex> достижимы нетерминалы <tex>A</tex>, <tex>B</tex>, <tex>C</tex> и <tex>D</tex>. Добавим их в множество и получим  <tex>\lbrace S, A, B, C, D \rbrace</tex>.
# Множество изменилось. Рассмотрим следующие элементы в нём. Из <tex>B</tex>, <tex>C</tex> и <tex>D</tex> нельзя вывести нетермиалы, а из <tex>A</tex> можно вывести <tex>E</tex> и <tex>F</tex>.
+
# Множество изменилось. Переберём заново правила из грамматики. Из <tex>A</tex> можно вывести <tex>E</tex> и <tex>F</tex>, добавим их в множество.
# Полученное множество нетерминалов будет таким: <tex>\lbrace S, A, B, C, D, E, F \rbrace</tex>. Больше оно меняться не будет.
+
# Снова переберём правила. Из <tex>C</tex> можно вывести только терминал, а <tex>G</tex> нет в множестве.
 +
# После последнего обхода правил грамматики множество не изменилось, значит мы нашли все достижимые нетерминалы: <tex>\lbrace S, A, B, C, D, E, F \rbrace</tex>.
 
# Теперь удалим правило <tex>G\rightarrow AD</tex>, так как оно содержит в левой части нетерминал, которого нет в полученном множестве.
 
# Теперь удалим правило <tex>G\rightarrow AD</tex>, так как оно содержит в левой части нетерминал, которого нет в полученном множестве.
  
 
== Полезные и бесполезные нетерминалы ==
 
== Полезные и бесполезные нетерминалы ==
 +
===Описание===
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Нетерминал <tex>A</tex> называется '''полезным''' в КС-грамматике <tex>\Gamma</tex>, если он может участвовать в выводе, то есть существует порождение вида <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* w</tex>. Иначе он называется '''бесполезным'''.
+
Нетерминал <tex>A</tex> называется '''полезным''' (англ. ''useful'') в КС-грамматике <tex>\Gamma</tex>, если он может участвовать в выводе, то есть существует порождение вида <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* w</tex>. Иначе он называется '''бесполезным''' (англ. ''useless'').
 
}}
 
}}
  
Строка 68: Строка 100:
 
Грамматика <tex>\Gamma</tex> не содержит бесполезных нетерминалов тогда и только тогда, когда грамматика <tex>\Gamma</tex> не содержит ни недостижимых нетерминалов, ни непорождающих.
 
Грамматика <tex>\Gamma</tex> не содержит бесполезных нетерминалов тогда и только тогда, когда грамматика <tex>\Gamma</tex> не содержит ни недостижимых нетерминалов, ни непорождающих.
 
|proof=
 
|proof=
''Необходимость.'' Очевидно, так как недостижимые и непорождающие нетерминалы являются бесполезными.
+
<tex>\Leftarrow</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> {{---}} не бесполезный.
+
<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> {{---}} не бесполезный.
 
}}
 
}}
  
== Алгоритм удаления бесполезных нетерминалов ==
+
===Алгоритм===
 +
Алгоритм состоит из двух этапов:
 
# Удалить из грамматики правила, содержащие непорождающие нетерминалы.
 
# Удалить из грамматики правила, содержащие непорождающие нетерминалы.
 
# Удалить из грамматики правила, содержащие недостижимые нетерминалы.
 
# Удалить из грамматики правила, содержащие недостижимые нетерминалы.
Строка 80: Строка 117:
 
Достаточность данных действий следует из доказанной выше теоремы.
 
Достаточность данных действий следует из доказанной выше теоремы.
  
Докажем, что после выполнения второго шага не могут появиться новые непорождающие нетерминалы.
+
{{Теорема
 
+
|id=th1
 +
|statement=
 +
После удаления из грамматики правил, содержащих недостижимые нетерминалы, не появятся новые непорождающие нетерминалы.
 +
|proof=
 
Допустим, что в грамматике появился непорождающий нетерминал <tex>A</tex>. Так как до удаления недостижимых нетерминалов существовал вывод из <tex>A</tex> некоторой конечной цепочки терминалов <tex>\omega</tex>, то было удалено хотя бы какое-то одно правило из этого вывода.
 
Допустим, что в грамматике появился непорождающий нетерминал <tex>A</tex>. Так как до удаления недостижимых нетерминалов существовал вывод из <tex>A</tex> некоторой конечной цепочки терминалов <tex>\omega</tex>, то было удалено хотя бы какое-то одно правило из этого вывода.
  
 
Пусть <tex>B\rightarrow\alpha</tex> {{---}} правило, первым из удалённых применяемое в выводе <tex>A \Rightarrow ^* \omega</tex>. Оно могло быть удалено только в том случае, если в <tex>\alpha</tex> присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то <tex>B</tex> — достижим, следовательно достижимы и все нетерминалы из <tex>\alpha</tex>. Значит, это правило не могло быть удалено.
 
Пусть <tex>B\rightarrow\alpha</tex> {{---}} правило, первым из удалённых применяемое в выводе <tex>A \Rightarrow ^* \omega</tex>. Оно могло быть удалено только в том случае, если в <tex>\alpha</tex> присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то <tex>B</tex> — достижим, следовательно достижимы и все нетерминалы из <tex>\alpha</tex>. Значит, это правило не могло быть удалено.
 +
}}
  
 
=== Пример ===
 
=== Пример ===
  
Пусть нам дана грамматика:
+
1. Пусть нам дана грамматика: <br>
<tex>
+
 
\begin{array}{l l} 
+
:<tex>
 
     S\rightarrow AS|BS|s \\
 
     S\rightarrow AS|BS|s \\
 
     E\rightarrow EF|FF \\
 
     E\rightarrow EF|FF \\
 
     A\rightarrow a \\
 
     A\rightarrow a \\
 
     F\rightarrow f
 
     F\rightarrow f
 +
</tex><br>
 +
2. Удалим правила, содержащие непорождающие нетерминалы: <br>
  
\end{array}
+
:<tex>
</tex>.<br>
 
Удалим правила, содержащие непорождающие нетерминалы и получим грамматику
 
<tex>
 
\begin{array}{l l} 
 
 
     S\rightarrow AS|s \\
 
     S\rightarrow AS|s \\
 
     E\rightarrow EF|FF \\
 
     E\rightarrow EF|FF \\
 
     A\rightarrow a \\
 
     A\rightarrow a \\
 
     F\rightarrow f
 
     F\rightarrow f
 +
</tex><br>
 +
3. Теперь удалим недостижимые нетерминалы:<br>
  
\end{array}
+
:<tex>
</tex>.<br>
 
Теперь удалим недостижимые нетерминалы и получим грамматику
 
<tex>
 
\begin{array}{l l} 
 
 
     S\rightarrow AS|s \\     
 
     S\rightarrow AS|s \\     
 
     A\rightarrow a
 
     A\rightarrow a
\end{array}
+
</tex>
</tex>.
 
  
 
=== Замечание ===
 
=== Замечание ===
 
Шаги алгоритма нельзя менять местами.  
 
Шаги алгоритма нельзя менять местами.  
  
Рассмотрим следующую грамматику:
+
Рассмотрим следующую грамматику: <br>
<tex>
+
 
\begin{array}{l l} 
+
:<tex>
 
     S\rightarrow AB|a \\
 
     S\rightarrow AB|a \\
 
     A\rightarrow b
 
     A\rightarrow b
\end{array}.
 
 
</tex>
 
</tex>
 +
 
Все нетерминалы в этой грамматике достижимы. Однако, если удалить <tex>B</tex> как непорождающий, то нетерминал <tex>A</tex> станет недостижимым.
 
Все нетерминалы в этой грамматике достижимы. Однако, если удалить <tex>B</tex> как непорождающий, то нетерминал <tex>A</tex> станет недостижимым.
 +
== См. также  ==
 +
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
 +
* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]
  
== Литература ==
+
== Источники информации ==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
+
* [[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 (рус.)
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Контекстно-свободные грамматики]]
 
[[Категория: Контекстно-свободные грамматики]]
 +
[[Категория: Нормальные формы КС-грамматик]]

Текущая версия на 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 (рус.)