Удаление бесполезных символов из грамматики — различия между версиями
Kirelagin (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показана 41 промежуточная версия 13 участников) | |||
Строка 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> | ||
+ | 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>\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''). |
}} | }} | ||
Строка 50: | Строка 98: | ||
|id=th1 | |id=th1 | ||
|statement= | |statement= | ||
− | Грамматика <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> {{---}} не бесполезный. | ||
}} | }} | ||
− | + | ===Алгоритм=== | |
− | == Алгоритм | + | Алгоритм состоит из двух этапов: |
# Удалить из грамматики правила, содержащие непорождающие нетерминалы. | # Удалить из грамматики правила, содержащие непорождающие нетерминалы. | ||
# Удалить из грамматики правила, содержащие недостижимые нетерминалы. | # Удалить из грамматики правила, содержащие недостижимые нетерминалы. | ||
+ | === Корректность алгоритма === | ||
+ | Достаточность данных действий следует из доказанной выше теоремы. | ||
{{Теорема | {{Теорема | ||
− | |id= | + | |id=th1 |
|statement= | |statement= | ||
− | + | После удаления из грамматики правил, содержащих недостижимые нетерминалы, не появятся новые непорождающие нетерминалы. | |
|proof= | |proof= | ||
− | + | Допустим, что в грамматике появился непорождающий нетерминал <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> | + | |
− | + | 1. Пусть нам дана грамматика: <br> | |
+ | |||
+ | :<tex> | ||
+ | S\rightarrow AS|BS|s \\ | ||
+ | E\rightarrow EF|FF \\ | ||
+ | A\rightarrow a \\ | ||
+ | F\rightarrow f | ||
+ | </tex><br> | ||
+ | 2. Удалим правила, содержащие непорождающие нетерминалы: <br> | ||
+ | |||
+ | :<tex> | ||
+ | S\rightarrow AS|s \\ | ||
+ | E\rightarrow EF|FF \\ | ||
+ | A\rightarrow a \\ | ||
+ | F\rightarrow f | ||
+ | </tex><br> | ||
+ | 3. Теперь удалим недостижимые нетерминалы:<br> | ||
+ | |||
+ | :<tex> | ||
+ | S\rightarrow AS|s \\ | ||
+ | A\rightarrow a | ||
+ | </tex> | ||
+ | |||
+ | === Замечание === | ||
+ | Шаги алгоритма нельзя менять местами. | ||
+ | |||
+ | Рассмотрим следующую грамматику: <br> | ||
+ | |||
+ | :<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 (рус.)