Содержание
Порождающие и непорождающие нетерминалы [ править ]
| Определение: |
| Нетерминал [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
[/math] порождающим или нет, - [math]\mathrm
- [math]\mathrm
[/math] список номеров правил, в правой части которых он встречается, - [math]\mathrm
[/math] — очередь нетерминалов, помеченных порождающими, но ещё не обработанных.
Вначале для всех нетерминалов в [math]\mathrm
Пока в очереди есть элементы, достаём очередной нетерминал и уменьшаем [math]\mathrm
Каждый из нетерминалов попадёт в очередь только один раз, следовательно мы пройдем по списку правил, в правой части которых он встречается, один раз. Таким образом, суммарно получаем [math]O(\left| \Gamma \right|)[/math] .
Рассмотрим следующую грамматику:
[math] S\rightarrow Ac\\ A\rightarrow SD\\ D\rightarrow aD\\ A\rightarrow a [/math]
Применяя описанный алгоритм:
- Изначально множество порождающих нетерминалов состоит из одного элемента [math]A[/math] .
- Добавим в множество нетерминал [math]S[/math] , так как существует правило [math]S\rightarrow Ac[/math] , в правой части которого стоят нетерминал [math]A[/math] , который есть в множестве, и терминал [math]c[/math] .
- После следующего обхода правил из грамматики множество не изменится.
- Теперь удалим правила [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]
Применяя описанный алгоритм:
- Возьмём множество, состоящее из единственного элемента: [math]\lbrace S \rbrace[/math] .
- Из [math]S[/math] достижимы нетерминалы [math]A[/math] , [math]B[/math] , [math]C[/math] и [math]D[/math] . Добавим их в множество и получим [math]\lbrace S, A, B, C, D \rbrace[/math] .
- Множество изменилось. Переберём заново правила из грамматики. Из [math]A[/math] можно вывести [math]E[/math] и [math]F[/math] , добавим их в множество.
- Снова переберём правила. Из [math]C[/math] можно вывести только терминал, а [math]G[/math] нет в множестве.
- После последнего обхода правил грамматики множество не изменилось, значит мы нашли все достижимые нетерминалы: [math]\lbrace S, A, B, C, D, E, F \rbrace[/math] .
- Теперь удалим правило [math]G\rightarrow AD[/math] , так как оно содержит в левой части нетерминал, которого нет в полученном множестве.
Полезные и бесполезные нетерминалы [ править ]
| Определение: |
| Нетерминал [math]A[/math] называется полезным (англ. useful) в КС-грамматике [math]\Gamma[/math] , если он может участвовать в выводе, то есть существует порождение вида [math]S \Rightarrow ^* \alpha A \beta \Rightarrow ^* w[/math] . Иначе он называется бесполезным (англ. useless). |
| Теорема: |
| Доказательство: |
| [math]\triangleright[/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] |
Алгоритм состоит из двух этапов:
- Удалить из грамматики правила, содержащие непорождающие нетерминалы.
- Удалить из грамматики правила, содержащие недостижимые нетерминалы.
Достаточность данных действий следует из доказанной выше теоремы.
| Теорема: |
| Доказательство: |
| [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] станет недостижимым.
В грамматике G(VT,VN,P,S) символ AVN называется бесплодным, если для него выполняется: = , то есть нетерминальный символ является бесплодным тогда, когда из него нельзя вывести ни одной цепочки терминальных символов.
В простейшем случае символ является бесплодным, если во всех правилах, где этот символ стоит в левой части, он также встречается и в правой части. Более сложные варианты предполагают зависимости между цепочками бесплодных символов, когда они в любой последовательности вывода порождают друг друга.
Для удаления бесплодных символов используется специальный алгоритм удаления бесплодных символов. Он работает со специальным множеством нетерминальных символов Yi. Первоначально в это множество попадают только те символы, из которых непосредственно можно вывести терминальные цепочки, затем оно пополняется на основе правил грамматики G.
Алгоритм удаления бесплодных символов по шагам
3. Если YiYi-1, то i:= i+1 и перейти к шагу 2, иначе перейти к шагу 4.
4. VN’ = Yi, VT’ = VT, в P’ входят те правила из Р, которые содержат только символы из множества (VTYi), S’ = S.
3.3.5. Устранение -правил
-правилами (или правилами с пустой цепочкой) называются все правила грамматики вида А, где AVN.
Грамматика G(VT,VN,P,S) называется грамматикой без -правил, если в ней не существует правил (А)Р, AS и существует только одно правило (S)P, в том случае, когда L(G), и при этом S не встречается в правой части ни одного правила грамматики.
Для того чтобы упростить построение распознавателей цепочек языка L(G), любую грамматику G целесообразно преобразовать к виду без -правил. Существует алгоритм преобразования произвольной КС-грамматики к виду без -правил. Он работает с некоторым множеством нетерминальных символов Wi.
Алгоритм устранения -правил по шагам
3. Если WiWi-1, то i:= i+1 и перейти к шагу 2, иначе перейти к шагу 4.
4. VN’ = VN, VT’ = VT, в P’ входят все правила из Р, кроме правил вида А.
5. Если (А?)Р и в цепочку ? входят символы из множества Wi, тогда на основе цепочки ? строится множество цепочек путем исключения из ? всех возможных комбинаций символов из Wi, и все правила вида А?’ добавляются в Р’.
6. Если SWi, то значит L(G), и тогда в VN’ добавляется новый символ S’, который становится целевым символом грамматики G’, а в Р’ добавляются два новых правила: S’|S; иначе S’ = S.
Данный алгоритм часто ведет к увеличению количества правил грамматики, но позволяет упростить построение распознавателя для заданного языка.
Устранение цепных правил
Циклом (циклическим выводом) в грамматике G(VT,VN,P,S) называется вывод вида А*А, AVN. Очевидно, что такой вывод абсолютно бесполезен. Поэтому в распознавателях КС-языков целесообразно избегать возможности появления циклов.
Циклы возможны только в том случае, если в КС-грамматике присутствуют цепные правила вида АВ, A,BVN. Чтобы исключить возможность появления циклов в цепочках вывода, достаточно устранить цепные правила из набора правил грамматики.
Чтобы устранить цепные правила в КС-грамматике G(VT,VN,P,S), для каждого нетерминального символа XVN строится специальное множество цепных символов Nx, а затем на основании построенных множеств выполняются преобразования правил Р. Поэтому алгоритм устранения цепных правил надо выполнить для всех нетерминальных символов грамматики из множества VN.
Алгоритм устранения цепных правил по шагам
1. Для всех символов Х из множества VN повторять шаги 1–4, затем перейти к шагу 5.
4. Если NXi NXi-1, то i:=i+1 и перейти к шагу 2, иначе NX= NXi–
5. VN’ = VN, VT’ = VT, в Р’ входят все правила из Р, кроме правил вида АВ, S’=S.
6. Для всех правил (А?)Р’, если BNА, BA, то в Р’ добавляются правила вида В?.
Данный алгоритм, так же как и алгоритм устранения -правил, ведет к увеличению числа правил грамматики, но упрощает построение распознавателей.
Если вы не помните, какие шрифтовые параметры были применены вами к тому или иному фрагменту текста, или если форматирование осуществляли не вы,…
Данные. Символ отображает данные, носитель данных не определен. Процесс. Символ отображает функцию обработки данных любого вида (выполнение определенной…
Устраните лишние символы из грамматики (Контекстно-свободные грамматики)
Помогите пожалуйста.
Ввод только определенных символов, удаление запрещенных символов из ячейки ввода
Добрый вечер! Подскажите, пожалуйста, как можно такое реализовать посредством jQuery. Вот форма: .
Вставка в строку нескольких символов и удаление символов из строки
не могу найти информацию про это:( какими операторами это делается?
Удаление из имён файлов определённых символов и сочетаний символов
Есть много обложек и в названиях присутствуют знаки «%2C+» и «+» (без кавычек) пример.
Удаление из массива символов символов от A до Z
Лаба по компьютерным сетям. Выполняется в CLR, поэтому через string не решить, т.к так функция.
но не на том уровне абстракции на котором его наклепали. нашел по русски а не математически написаный алгоритм. Он легок в понимании хотябы. Алгоритм тот что был с мат закорючками выкладывать не буду они эквивалентны как я понял. Вот эту разъяснялку нашел:
1)Отметить(выделить) вершины графа, помеченные терминальными символами, а также вершину е, если такая имеется.
2) Если в Р есть правила А>ь, где ь состит из символов уже помеченных вершин, а вершина А еще не отмечена, то отметить эту вершину. Повторять шаг 2 пока возможно.
3) Из грамматики удалить символы неотмеченных вершин, а также правила, содержащие хотя бы один символ неотмеченной вершины.
по истолкованому на нормальном языке алгоритму я более или менее представляю себе реализацию, единственную проблему мне могут выдать строки. Мне придется отмечать символы. создавать таблицу где будет указано какие символы отмечены какие нет. анализировать строки раз за разом на предмет наличия неотмеченых символов которые надо отметить. если будут более легкие решения и умные мысли выкладывайте мне полезно будет.
заранее благодарен
| 23.10.2010, 17:02 |
| 23.10.2010, 17:02 |
|
Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь. Удаление символов удаление символов detector |