Операции над А-языками

Теорема 5.6. Автоматные языки замкнуты относительно операций объединения, конкатенации, итерации, обращения, подстановки, пересечения, дополнения и разности.

Доказательство. Проведем его конструктивно, также как и в теореме 5.4. Для представления А-грамматик используем графы состояний и в случае операций над двумя языками индексируем нетерминалы исходных грамматик.

Объединение. Пусть даны два А-языка L₁=L(G₁) и L₂=L(G₂) и графы состояний грамматик G₁ и G₂ схематично представлены на рисунках 5.2 (а) и (б), соответственно.

На рисунке 5.2 (в) представлена грамматика G, определяющая объединение исходных языков. Для ее построения вводим новый начальный символ S. Если в исходных грамматиках из S _i в A _i ведет ребро, помеченное терминалом a, то проведем ребро из S в A _i и пометим его тем же терминалом a. Выберем новый конечный символ F и все ребра, шедшие в F₁ и F₂ проведем в F, а F₁ и F₂ удалим. Вершины S₁ и S₂ в общем случае удалять нельзя, так как к ним могут идти ребра, но если в S _i возвратов нет, то эту вершину (нетерминал) можно удалить (в нашем примере можно удалить вершину S₂ вместе с выходящими из нее дугами).

Очевидно, что результирующая грамматика G является А-грамматикой. Зачастую, она может быть недетерминированной, но перевод А-грамматики из недетерминированной формы в детерминированную уже был рассмотрен в разделе 3.1.

Конкатенация. В этом случае, получение грамматики-результата сводится к склеиванию начальной вершины S₂ языка-суффикса с заключительной вершиной F₁ языка-префикса, т.е. все ребра, шедшие в F₁ направляются в S₂, а F₁ удаляется (см. рис. 5.3 (а)).

Итерация. Для каждого ребра, идущего из некоторой вершины A исходной грамматики в заключительную вершину F строится дублирующее его ребро, ведущее из A в начальную вершину S. На рис. 5.3 (б) добавляемые ребра выделены жирной линией.

Обращение. На рис. 5.4 (а) представлен граф исходной грамматики. Изменим имя начальной вершины S на S₁ идобавим вершину S₂. Для всех ребер выходящих из S₁ и входящих в A добавим дуги выходящие из S₂ и входящие в A (см. рис. 5.4 (б)). Заменим имя заключительной вершины F на имя начальной - S, а имя вершины S₂ на имя заключительной - F и изменим ориентацию ребер. В результате мы получим А-грамматику, определяющую обращение исходного языка. Граф этой грамматики представлен на рис. 5.4 (в).

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

Подстановка. На рис 5.5 (а) представлена грамматика G₂ языка L₂, который мы хотим подставить вместо терминала a в язык L₁ с грамматикой G₁,приведенной на рис. 5.5 (б). Возьмем столько экземпляров G₂, сколько в G₁ имеется ребер, помеченных терминалом a. Нетерминалы в G₁ отметим индексом 0, а нетерминалы в i - ом экземпляре G₂ индексом i. На место каждого ребра G₁, помеченного терминалом a и идущего из A₀ в B₀, подставим экземпляр G₂, т.е. вершину A₀ из G₂ совместим с вершиной S_i, а вершину B₀ - с вершиной F_i. Отметим, что при наличии возвратов в начальную вершину грамматики G₂ и других ребер, идущих из A₀ грамматики G₁ и помеченных терминалами, отличными от a, необходимо расщеплять начальную вершину грамматики G₂ на две вершины. Одна из них в точности совпадает с исходной, а другая повторяет все выходы исходной начальной вершины, но возвраты в нее опускаются. Именно эту, вторую начальную вершину без возвратов и совмещают с A₀. Результаты этих преобразований приведены на рис. 5.5 (в), отражающем грамматику языка, полученного в результате указанной подстановки.

Пересечение. Здесь мы отойдем от принятого выше представления А-грамматик в виде графов состояний и рассмотрим построение грамматики, определяющей пересечение двух А-языков на конкретном примере.

Пример 5.3. Пусть А-язык L₁ определяется А-грамматикой G₁=(N₁,S₁,P₁,S) и множество P₁ - это группа модифицированных правил

S ® aS ½ bC ½ dC

C ® bC ½ cC ½ûë F,

где F - заключительный нетерминал, и А-язык L₂ определяется А-грамматикой G₂=(N₂,S₂,P₂,R) и

Определим грамматику G=(N, S, P, <SR>) языка L = L₁Ç L₂. Для того, чтобы проконтролировать наше решение вначале определим вид цепочек, как заданных языков, так и языка - результата, благо простота выбранных грамматик позволяет легко это сделать. Цепочки языка L₁ могут содержать в начале произвольное количество символов a, обязательный символ b или d, затем, возможно, серию символов b и (или) c и в завершении символ ûë. Схематично цепочку языка L₁ можно представить в виде , где квадратные скобки ограничивают необязательные части строки, многоточие обозначает произвольное количество символов, а две строки - произвол в выборе символов. Цепочки языка L₂ имеют вид или , а цепочка результирующего языка - .

Заметим, что S Í S₁Ç S₂. Построение грамматики-пересечения напоминает построение детерминированной формы А-грамматики. В качестве элементов нового множества нетерминалов выбираются пары нетерминалов исходных грамматик, типа <SR>, <SQ>, <SM>, <CM>, <CQ> и т.п. В результате построения правил грамматики-пересечения часть этих нетерминалов может быть исключена, как внутренние или внешние тупики. Схема построения правил новой грамматики состоит в том, что рассматриваются только те пары нетерминалов и те их альтернативы, которые имеют одни и те же терминалы в качестве продолжения цепочки. В результате мы получим грамматику

<SR> ® a<SQ> ½ b<CM>

<SQ> ® b<CQ>

<CQ> ® b<CQ> ½ûë <FF>

Заметим, что нетерминал <CM> не имеет общего продолжения, является внешним тупиком и его можно исключить вместе с правилом <SR> ® b<CM>. †

Опустим здесь доказательства двух последних положений теоремы, так как они не имеют практических приложений. †

Дата добавления: 2015-06-27