Что такое бесплодные символы

Удаление бесплодных символов

В простейшем случае символ является бесплодным, если во всех правилах, где этот символ стоит в левой части, он также встречается и в правой части. Более сложные варианты предполагают зависимости между цепочками бесплодных символов, когда они в любой последовательности вывода порождают друг друга.

Для удаления бесплодных символов используется специальный алгоритм удаления бесплодных символов. Он работает со специальным множеством нетерминальных символов Yi. Первоначально в это множество попадают только те символы, из которых непосредственно можно вывести терминальные цепочки, затем оно пополняется на основе правил грамматики G.

Алгоритм удаления бесплодных символов по шагам

3. Если YiYi-1, то i:= i+1 и перейти к шагу 2, иначе перейти к шагу 4.

4. VN’ = Yi, VT’ = VT, в P’ входят те правила из Р, которые содержат только символы из множества (VTYi), S’ = S.

3.3.5. Устранение -правил

-правилами (или правилами с пустой цепочкой) называются все правила грамматики вида А, где AVN.

Грамматика G(VT,VN,P,S) называется грамматикой без -правил, если в ней не существует правил (А)Р, AS и существует только одно правило (S)P, в том случае, когда L(G), и при этом S не встречается в правой части ни одного правила грамматики.

Для того чтобы упростить построение распознавателей цепочек языка L(G), любую грамматику G целесообразно преобразовать к виду без -правил. Существует алгоритм преобразования произвольной КС-грамматики к виду без -правил. Он работает с некоторым множеством нетерминальных символов Wi.

Алгоритм устранения -правил по шагам

3. Если WiWi-1, то i:= i+1 и перейти к шагу 2, иначе перейти к шагу 4.

4. VN’ = VN, VT’ = VT, в P’ входят все правила из Р, кроме правил вида А.

6. Если SWi, то значит L(G), и тогда в VN’ добавляется новый символ S’, который становится целевым символом грамматики G’, а в Р’ добавляются два новых правила: S’|S; иначе S’ = S.

Данный алгоритм часто ведет к увеличению количества правил грамматики, но позволяет упростить построение распознавателя для заданного языка.

Устранение цепных правил

Циклом (циклическим выводом) в грамматике G(VT,VN,P,S) называется вывод вида А*А, AVN. Очевидно, что такой вывод абсолютно бесполезен. Поэтому в распознавателях КС-языков целесообразно избегать возможности появления циклов.

Циклы возможны только в том случае, если в КС-грамматике присутствуют цепные правила вида АВ, A,BVN. Чтобы исключить возможность появления циклов в цепочках вывода, достаточно устранить цепные правила из набора правил грамматики.

Чтобы устранить цепные правила в КС-грамматике G(VT,VN,P,S), для каждого нетерминального символа XVN строится специальное множество цепных символов Nx, а затем на основании построенных множеств выполняются преобразования правил Р. Поэтому алгоритм устранения цепных правил надо выполнить для всех нетерминальных символов грамматики из множества VN.

Алгоритм устранения цепных правил по шагам

1. Для всех символов Х из множества VN повторять шаги 1–4, затем перейти к шагу 5.

4. Если NXi NXi-1, то i:=i+1 и перейти к шагу 2, иначе NX= NXi– и перейти к шагу 1.

5. VN’ = VN, VT’ = VT, в Р’ входят все правила из Р, кроме правил вида АВ, S’=S.

6. Для всех правил (А?)Р’, если BNА, BA, то в Р’ добавляются правила вида В?.

Данный алгоритм, так же как и алгоритм устранения -правил, ведет к увеличению числа правил грамматики, но упрощает построение распознавателей.

Статьи к прочтению:

Похожие статьи:

Если вы не помните, какие шрифтовые параметры были применены вами к тому или иному фрагменту текста, или если форматирование осуществляли не вы,…

Данные. Символ отображает данные, носитель данных не определен. Процесс. Символ отображает функцию обработки данных любого вида (выполнение определенной…

Источник

Приведёнными (или грамматиками в каноническом виде) называются грамматики, которые не содержат недостижимых и бесплодных символов, циклов и пустых правил (l-правил).

Рассмотрим некоторую грамматику G(VT,VN,P,S) и дадим необходимые определения.

Нетерминальный символ AÎVN называется бесплодным (или бесполезным), если из него нельзя вывести ни одной цепочки терминальных символов, т.е. =Æ.

В простейшем случае символ является бесплодным, если во всех правилах, где он находится в левой части, он встречается также и в правой части. В более сложных случаях бесполезные символы могут находиться в некоторой взаимной зависимости, порождая друг друга. Если из правил грамматики удалить такие символы, то эти правила станут проще.

Символ xÎ(VTÈVN) называется недостижимым, если он не встречается ни в одной сентенциальной форме грамматики G. Это значит, что он не может появиться ни в одной цепочке вывода. Для исключения всех недостижимых символов не обязательно рассматривать все сентенциальные формы грамматики, достаточно воспользоваться специальным алгоритмом удаления недостижимых символов. После удаления таких символов правила также упрощаются.

l-правилами, или правилами с пустой цепочкой, называются все правила грамматики вида A®l, AÎVN. Грамматика G называется грамматикой без l-правил, если в ней нет правил вида (A®l), AÎVN, A¹S, и существует только одно правило (S®l)ÎP, если lÎL(G) и при этом S не встречается в правой части ни одного правила грамматики G. Для упрощения процесса построения распознавателя цепочек языка L(G) любую грамматику целесообразно привести к виду без l-правил.

Циклом в грамматике G называется вывод вида AÞ*A, AÎVN. Очевидно, что такой вывод бесполезен, поэтому в распознавателях КС-языков рекомендуется избегать возможности появления циклов.

Циклы возможны в случае существования в грамматике цепных правил вида A®B, A,BÎVN. Достаточно устранить цепные правила из набора правил грамматики, чтобы исключить возможность появления циклов.

Для того чтобы преобразовать произвольную КС-грамматику к каноническому виду, необходимо выполнить следующие действия (причём именно в том порядке, каком они перечислены):

§ удалить все бесплодные символы;

§ удалить все недостижимые символы;

§ удалить цепные правила.

Для каждого из названных действий существует свой алгоритм. Рассмотрим эти алгоритмы в том порядке, каком требуется их реализовывать.

1 Удаление бесплодных символов

Выполняется пошаговое построение множества Y_i, которое не содержит бесплодных символов рассматриваемой грамматики. На каждом шаге к уже построенному множеству добавляются новые нетерминальные символы. При этом первоначально в него включают те символы, из которых могут быть выведены терминальные цепочки, а на последующих шагах – символы, из которых могут быть выведены цепочки, состоящие как из терминальных символов, так и из символов уже построенного множества. После того, как с некоторого шага множество Y_i перестанет изменяться, процесс построения считается законченным. В итоговое множество нетерминальных символов должны входить только символы из построенного множества Y_i.

3. До тех пор, пока не станет Y_i=Y_i–1, выполняется i:=i+1 и снова шаг 2.

4. Новая грамматика: множество терминальных символов VT¢ совпадает со старым VT: VT¢=VT, VN¢=Y_i, S¢=S, а в P¢ входят те правила из P, которые содержат только символы из множества (Y_iÈVT).

2 Удаление недостижимых символов

Данный алгоритм строит множество достижимых символов V_i исходной грамматики. Сначала в это множество входит только целевой символ S грамматики G, затем оно пополняется на основе правил этой грамматики. Множество считается построенным, если в него невозможно добавить ничего нового. Все символы, не вошедшие в это множество, являются недостижимыми, следовательно, их требуется исключить из словаря и из правил грамматики.

3. До тех пор, пока не станет V_i=V_i–1, выполняется i:=i+1 и снова шаг 2.

4. Новая грамматика: множество терминальных символов VT¢=VTÇV_i, множество нетерминальных символов VN¢= VNÇV_i, S¢=S, а в P¢ входят те правила из P, которые содержат только символы из множества V_i.

Оба рассмотренных алгоритма – удаления бесплодных и недостижимых символов – относятся к первой группе алгоритмов, т.е. их применение приводит к упрощению грамматики, сокращению количества правил и уменьшению объема алфавита.

Пример работы рассмотренных алгоритмов:

Источник

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

Содержание

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

Описание [ править ]

Определение:

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

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

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

Алгоритм [ править ]

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

Время работы алгоритма [ править ]

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

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

Пример [ править ]

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

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

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

Достижимые и недостижимые нетерминалы [ править ]

Описание [ править ]

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

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

Алгоритм [ править ]

Время работы алгоритма [ править ]

Пример [ править ]

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

[math] S\rightarrow AB|CD\\ A\rightarrow EF\\ G\rightarrow AD\\ C\rightarrow c [/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)

Выход: КС-грамматика G’ = (VT’, VN’, P’, S), не содержащая недостижимых символов, для которой L(G) = L(G’).

Определение: КС-грамматика G называется приведенной, если в ней нет недостижимых и бесплодных символов.

Алгоритм приведения грамматики :

обнаруживаются и удаляются все бесплодные нетерминалы.

обнаруживаются и удаляются все недостижимые символы.

Удаление символов сопровождается удалением правил вывода, содержащих эти символы.

Замечание: е сли в этом алгоритме переставить шаги (1) и (2), то не всегда результатом будет приведенная грамматика.

Для описания синтаксиса языков программирования стараются использовать однозначные приведенные КС-грамматики.

Исключение цепных правил

Идея доказательства заключается в следующем.

Если грамматика G имеет правила A  B, B  C, C  aX, то такие правила могут быть заменены одним правилом А  aX, поскольку вывод A   B  C  aX цепочки aX в грамматике G может быть получен в грамматике G’ с помощью правила A  aX.

В общем случае доказательство последнего утверждения можно выполнить так.

В качестве примера выполним исключение цепных правил из грамматики G :

Вначале разобьем правила грамматики на два подмножества:

Для каждого правила из P1 построим соответствующее подмножество.

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

Преобразование неукорачивающих грамматик

Последний вид рассматриваемых преобразований связан с удалением из грамматики правил с пустой правой частью.

1)схема грамматики не содержит аннулирующих правил,

Для грамматик, содержащих аннулирующие правила, справедливо следующее утверждение.

Построение неукорачивающей грамматики приведет к увеличению числа правил заданной грамматики из-за построения дополнительных правил, получаемых в результате исключения нетерминалов аннулирующих правил. Чтобы построить дополнительные правила необходимо выполнить все возможные подстановки пустой цепочки вместо аннулирующего нетерминала во все правила грамматики.

Если же в грамматике есть правило вида S  , где S – начальный символ грамматики, и символ S входит в правые части других правил грамматики, то следует ввести новый начальный символ S’ и заменить правило S   двумя новыми правилами: S’   и S’  S.

В качестве иллюстрации способа построения неукорачивающих грамматик, исключим аннулирующие правила из следующей грамматики:

Выполняя все возможные замены символа S в первом правиле грамматики, получаем четыре правила вида:

Поступая аналогично со вторым правилом, имеем:

S bSaS, S baS, S  bSa, S  ba.

Учитывая, что начальный символ, образующий аннулирующее правило, входит в правые части других правил грамматики, заменим правило S   правилами вида S’   и S’  S.

Построенная совокупность правил образует множество правил искомой неукорачивающей грамматики.

S  aSbS | abS | aSb | ab | bSaS |baS | bSa | ba

Все приведенные выше преобразования грамматик могут быть использованы при построении как конечных, так и магазинных автоматов.

КС-грамматики в нормальной форме

Грамматики в нормальной форме Хомского

Нормальная форма Хомского или бинарная нормальная форма (БНФ) — это одна из предопределенных форм для правил КС-грамматики. В нормальную форму Хомского можно преобразовать любую произвольную КС-грамматику. Для пре­образования в нормальную форму Хомского предварительно грамматику надо преобразовать в приведенный вид.

Определение нормальной формы Хомского

КС-грамматика G(VT,VN,P,S) называется грамматикой в нормальной форме Хомского, если в ее множестве правил Р присутствуют только правила следую­щего вида:

2. А  а, где AeVN и aVT.

Никакие другие формы правил не должны встречаться среди правил граммати­ки в нормальной форме Хомского [6, т. 1, 26].

КС-грамматика в нормальной форме Хомского называется также грамматикой в бинарной нормальной форме (БНФ). Название «бинарная» происходит от того, что на каждом шаге вывода в такой грамматике один нетерминальный символ может быть заменен только на два других нетерминальных символа. Поэтому в дереве вывода грамматики в нормальной форме Хомского каждая вершина либо распадается на две другие вершины (в соответствии с первым видом правил), либо содержит один последующий лист с терминальным символом (в соответст­вии со вторым видом правил) Третий вид правил введен для того, чтобы к нор­мальной форме Хомского можно было преобразовывать грамматики КС-языков, содержащих пустые цепочки символов.

Алгоритм преобразования грамматики в нормальную форму Хомского

Алгоритм позволяет преобразовать произвольную исходную КС-грамматику в эквивалентную грамматику в нормальной форме Хомского.

На первом шаге исходную грамматику надо преобразовать к приведенному виду. Поскольку алгоритм преобразования КС-грамматик к приведенному виду был рассмотрен выше, можно считать, что исходная грамматика уже является приве­денной (не содержит бесполезных и недостижимых символов, цепных правил и -правил).

3. Если встречается правило вида S, где S — целевой символ грамматики G, то оно переносится во множество Р’ без изменений.

Пример преобразования грамматики в нормальную форму Хомского

Начнем разбирать правила этой грамматики.

Первое правило исходной грамматики SAaB подпадает под 7-й вариант рабо­ты алгоритма. В соответствии с требованиями алгоритма заменяем его на после­довательность:

Второе правило исходной грамматики S  Aa подпадает под 5-й вариант работы алгоритма. Заменяем его на два правила:

Новый символ добавляется во множество нетерминальных символов но­вой грамматики. Получаем VN’ = .

Третье правило исходной грамматики S  bc подпадает под 6-й вариант работы алгоритма. Заменяем его на три правила:

Четвертое правило исходной грамматики А  АВ подпадает под 2-й вариант рабо­ты алгоритма. Переносим его во множество правил новой грамматики без изме­нений.

Пятое правило исходной грамматики А  а подпадает под 1-й вариант работы ал­горитма. Переносим его во множество правил новой грамматики без изменений.

Шестое правило исходной грамматики А  аС подпадает под 4-й вариант работы алгоритма. Заменяем его на два правила:

Седьмое правило исходной грамматики В  Ва подпадает под 5-й вариант работы алгоритма. Заменяем его на два правила:

Восьмое правило исходной грамматики B  b подпадает под 1-й вариант работы алгоритма. Переносим его во множество правил новой грамматики без изменений.

Девятое правило исходной грамматики С->АВ подпадает под 2-й вариант работы алгоритма. Переносим его во множество правил новой грамматики без изменений.

Десятое правило исходной грамматики С-»с подпадает под 1-й вариант работы алгоритма. Переносим его во множество правил новой грамматики без изменений.

Рассмотрение множества правил исходной грамматики закончено. Множество правил Р’ новой грамматики G’ и множество нетерминальных символов VN’ этой грамматики окончательно построены. Целевым символом новой грамматики является символ S.

Видно, что при приведении грамматики к нормальной форме Хомского количество правил и нетерминальных символов в грамматике увеличивается. При этом врастет объем грамматики и несколько затрудняется ее восприятие человеком. Од­нако цель преобразования — не упрощение грамматики, а упрощение построе­ния распознавателя языка на ее основе. Именно этой цели и служит нормальная форма Хомского. Далее будут рассмотрены методы построения распознавателей, в основе которых лежит именно эта форма представления грамматики КС-языка.

Левая рекурсия в КС-грамматиках. Алгоритм устранения левой рекурсии из правил грамматики.

Способ построения эквивалентной грамматики заключается в следующем. Допустим, что исходная грамматика G содержит правила:

Рассмотрим построение выводов в G и G’.

В грамматике G вывод цепочки имеет вид:

в грамматике G’ эта же цепочка выводится так:

Чтобы показать технику преобразования, рассмотрим пример. Требуется преобразовать грамматику G (рассмотренную ранее), с правилами:

В результате получаем грамматику G ‘ с правилами:

не содержащую леворекурсивных правил.

Грамматики в нормальной форме Грейбах

На основании грамматики, в которой исключена левая рекурсия, можно построить грамматику в нормальной форме Грейбах.

S  , если L(G), причем S не должно встречаться в правых частях других правил.

Никакие другие формы правил не должны встречаться среди правил грамматики в нормальной форме Грейбах.

Нормальная форма Грейбах является удобной формой представления грамматик для построения нисходящих левосторонних распознавателей (в тех случаях, когда присутствие левой рекурсии в правилах грамматики недопустимо). Подробнее с нею можно познакомиться в [6, т. 1, 26].

Источник

Что такое бесплодные символы

Вопрос классификации знаков по степени их плодовитости можно решить самостоятельно, зная основные астрологические принципы.

Юлия, а бесплодность и плодовитость градусов Вы на своей практике проверяли?

	Leanita писал(а):
	Например, одна планета в бесплодном, другая в плодовитом: 1.аспект между ними, негативный (в данном контексте квадрат, оппозиция)-какая планета «сильнее» туда и «одеяло»?

Это зависит от характера планет, входящих в аспект: если напряженный аспект между сигнификатором деторождения и зловредной (бесплодной) планетой, аспект уже будет нести негативное влияние. Степень негатива в данном случае будет зависеть от плодовитости второй планеты и знаков, в которых обе планеты находятся.

	Leanita писал(а):
	2.аспект позитивный (секстиль, тригон)-та же схема.

По моим наблюдениям, гармоничные аспекты могут не спасать ситуацию, если большинство сигнификаторов в бесплодных или почти бесплодных знаках.
Пример из жизни:
— 5 дом во Льве, Дева включенный знак, в 5 доме Юпитер, Плутон, Уран в Деве;
— Солнце упр. 5-го и альмутен детей в той карте в Стрельце (7 дом) в трине с Луной в Овне (12 дом) и квадратуре с Плутоном в 5-м;
— Юпитер в 5-м в квадратуре с Меркурием (соупр. 5-го) в Стрельце (7 дом) и секстиле с Венерой в Скорпионе (6 дом);
— Меркурий также в секстиле с Марсом (10 дом) в Водолее и трине с Сатурном в Овне (12 дом).
Из существенно напряженных аспектов только квадратура Солнца с Плутоном при явном перевесе гармоничных аспектов сигнификаторов и наличии Юпитере в 5 доме в гармоничном аспекте с Венерой, но все тематические планеты находятся в мало плодовитых или бесплодных знаках + Юпитер слаб в Деве. В итоге: детей нет, несмотря на многочисленные попытки хозяйки карты забеременеть самыми разными способами, включая новые технологии.

	Leanita писал(а):
	3.соединение пока не разобралась куда отнести

Также зависит от качества планет и плодовитости знака, в котором планеты формируют соединение.

На стр. 58 (издания М., 2004 года) Лилли дается краткое схематическое описание:
Плодовитые: Рак, Скорпион, Рыбы
Бесплодно: Близнецы, Лев, Дева

На стр. 512 более подробное, развернутое описание (которое в начале темы процитировала Leanita, выполнив незначительное сокращение). В квадратных скобках я дописал свои дополнения/комментарии к тому, что говорит Лилли.

Источник