Удаление бесполезных символов из грамматики — различия между версиями
(→Достижимые и недостижимые нетерминалы) |
м (rollbackEdits.php mass rollback) |
||
(не показано 28 промежуточных версий 7 участников) | |||
Строка 1: | Строка 1: | ||
== Порождающие и непорождающие нетерминалы == | == Порождающие и непорождающие нетерминалы == | ||
+ | ===Описание=== | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | Нетерминал <tex>A</tex> называется '''порождающим''', если из него может быть выведена конечная терминальная цепочка. Иначе он называется '''непорождающим'''. | + | [[Формальные_грамматики|Нетерминал]] <tex>A</tex> называется '''порождающим''' (англ. ''generating''), если из него может быть выведена конечная терминальная цепочка. Иначе он называется '''непорождающим'''. |
}} | }} | ||
− | + | Очевидно, что если и только если все нетерминалы правой части правила являются порождающими, то порождающим является и нетерминал, стоящий в его левой части. | |
− | Очевидно, что если и только если все нетерминалы правой части являются порождающими, то порождающим является и нетерминал, стоящий | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
{{Лемма | {{Лемма | ||
|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''). |
}} | }} | ||
− | + | Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми. | |
− | Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
{{Лемма | {{Лемма | ||
|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> | + | |
− | + | :<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 | ||
− | |||
− | |||
</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>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>, так как оно содержит в левой части нетерминал, которого нет в полученном множестве. | # Теперь удалим правило <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>\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> | + | |
− | + | :<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> | ||
− | + | :<tex> | |
− | < | ||
− | |||
− | |||
− | |||
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> | ||
− | + | :<tex> | |
− | < | ||
− | |||
− | |||
− | |||
S\rightarrow AS|s \\ | S\rightarrow AS|s \\ | ||
A\rightarrow a | A\rightarrow a | ||
− | + | </tex> | |
− | </tex> | ||
=== Замечание === | === Замечание === | ||
Шаги алгоритма нельзя менять местами. | Шаги алгоритма нельзя менять местами. | ||
− | Рассмотрим следующую грамматику: | + | Рассмотрим следующую грамматику: <br> |
− | <tex> | + | |
− | + | :<tex> | |
S\rightarrow AB|a \\ | S\rightarrow AB|a \\ | ||
A\rightarrow b | A\rightarrow b | ||
− | |||
</tex> | </tex> | ||
+ | |||
Все нетерминалы в этой грамматике достижимы. Однако, если удалить <tex>B</tex> как непорождающий, то нетерминал <tex>A</tex> станет недостижимым. | Все нетерминалы в этой грамматике достижимы. Однако, если удалить <tex>B</tex> как непорождающий, то нетерминал <tex>A</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 (рус.) | ||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
[[Категория: Контекстно-свободные грамматики]] | [[Категория: Контекстно-свободные грамматики]] | ||
+ | [[Категория: Нормальные формы КС-грамматик]] |
Текущая версия на 19:21, 4 сентября 2022
Порождающие и непорождающие нетерминалы
Описание
Определение: |
Нетерминал называется порождающим (англ. generating), если из него может быть выведена конечная терминальная цепочка. Иначе он называется непорождающим. |
Очевидно, что если и только если все нетерминалы правой части правила являются порождающими, то порождающим является и нетерминал, стоящий в его левой части.
Лемма: |
После удаления из грамматики правил, содержащих непорождающие нетерминалы, язык не изменится. |
Доказательство: |
Непорождающие нетерминалы по определению не могли участвовать в выводе какого-либо слова. |
Алгоритм
Шаг 0. Множество порождающих нетерминалов пустое.
Шаг 1. Находим правила, не содержащие нетерминалов в правых частях и добавляем нетерминалы, встречающихся в левых частях таких правил, в множество.
Шаг 2. Если найдено такое правило, что все нетерминалы, стоящие в его правой части, уже входят в множество, то добавим в множество нетерминалы, стоящие в его левой части.
Шаг 3. Повторим предыдущий шаг, если множество порождающих нетерминалов изменилось.
В результате получаем множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.
Время работы алгоритма
Данный алгоритм работает за очередь можно ускорить его до .
, где — размер грамматики. Однако используяМодификация алгоритма с очередью
Для реализации алгоритма поиска непорождающих нетерминалов будем использовать следующие структуры:
- — является ли нетерминал порождающим или нет,
- — счетчик количества нетерминалов, которые ещё не помечены порождающими, для каждого из правил,
- — для каждого нетерминала список номеров правил, в правой части которых он встречается,
- — очередь нетерминалов, помеченных порождающими, но ещё не обработанных.
Вначале для всех нетерминалов в
Пока в очереди есть элементы, достаём очередной нетерминал и уменьшаем для всех правил из для данного нетерминала. Если счётчик количества порождающих терминалов обнулился, то добавим нетерминал, стоящий в левой части данного правила в очередь и пометим его порождающим.
Каждый из нетерминалов попадёт в очередь только один раз, следовательно мы пройдем по списку правил, в правой части которых он встречается, один раз. Таким образом, суммарно получаем .
Пример
Рассмотрим следующую грамматику:
Применяя описанный алгоритм:
- Изначально множество порождающих нетерминалов состоит из одного элемента .
- Добавим в множество нетерминал , так как существует правило , в правой части которого стоят нетерминал , который есть в множестве, и терминал .
- После следующего обхода правил из грамматики множество не изменится.
- Теперь удалим правила и , так как они содержат нетерминалы, которых нет в полученном множестве.
Достижимые и недостижимые нетерминалы
Описание
Определение: |
Нетерминал КС-грамматике , если существует порождение . Иначе он называется недостижимым (англ. unreachable). | называется достижимым (англ. reachable) в
Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми.
Лемма: |
После удаления из грамматики правил, содержащих недостижимые нетерминалы, язык не изменится. |
Доказательство: |
Недостижимые нетерминалы по определению не достижимы из стартового, следовательно они не могли участвовать в выводе какого-либо слова. |
Алгоритм
Шаг 0. Множество достижимых нетерминалов состоит из единственного элемента:
Шаг 1. Если найдено правило, в левой части которого стоит нетерминал, содержащийся в множестве, добавим в множество все нетерминалы из правой части.
Шаг 2. Повторим предыдущий шаг, если множество порождающих нетерминалов изменилось.
Получаем множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми.
Время работы алгоритма
Данный алгоритм работает за обход в глубину можно ускорить его до .
, однако используяПример
Рассмотрим следующую грамматику:
Применяя описанный алгоритм:
- Возьмём множество, состоящее из единственного элемента: .
- Из достижимы нетерминалы , , и . Добавим их в множество и получим .
- Множество изменилось. Переберём заново правила из грамматики. Из можно вывести и , добавим их в множество.
- Снова переберём правила. Из можно вывести только терминал, а нет в множестве.
- После последнего обхода правил грамматики множество не изменилось, значит мы нашли все достижимые нетерминалы: .
- Теперь удалим правило , так как оно содержит в левой части нетерминал, которого нет в полученном множестве.
Полезные и бесполезные нетерминалы
Описание
Определение: |
Нетерминал | называется полезным (англ. useful) в КС-грамматике , если он может участвовать в выводе, то есть существует порождение вида . Иначе он называется бесполезным (англ. useless).
Теорема: |
Грамматика не содержит бесполезных нетерминалов тогда и только тогда, когда грамматика не содержит ни недостижимых нетерминалов, ни непорождающих. |
Доказательство: |
|
Алгоритм
Алгоритм состоит из двух этапов:
- Удалить из грамматики правила, содержащие непорождающие нетерминалы.
- Удалить из грамматики правила, содержащие недостижимые нетерминалы.
Корректность алгоритма
Достаточность данных действий следует из доказанной выше теоремы.
Теорема: |
После удаления из грамматики правил, содержащих недостижимые нетерминалы, не появятся новые непорождающие нетерминалы. |
Доказательство: |
Допустим, что в грамматике появился непорождающий нетерминал Пусть . Так как до удаления недостижимых нетерминалов существовал вывод из некоторой конечной цепочки терминалов , то было удалено хотя бы какое-то одно правило из этого вывода. — правило, первым из удалённых применяемое в выводе . Оно могло быть удалено только в том случае, если в присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то — достижим, следовательно достижимы и все нетерминалы из . Значит, это правило не могло быть удалено. |
Пример
1. Пусть нам дана грамматика:
2. Удалим правила, содержащие непорождающие нетерминалы:
3. Теперь удалим недостижимые нетерминалы:
Замечание
Шаги алгоритма нельзя менять местами.
Рассмотрим следующую грамматику:
Все нетерминалы в этой грамматике достижимы. Однако, если удалить
как непорождающий, то нетерминал станет недостижимым.См. также
Источники информации
- Wikipedia — Formal grammar
- Wikipedia — Chomsky normal form
- Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)