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

Теорема 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 является А-грамматикой. Зачастую она может быть недетерминированной, но перевод А-грамматики из недетерминированной формы в детерминированную уже был рассмотрен ранее.

Конкатенация. В этом случае получение грамматики-результата сводится к склеиванию начальной вершины 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₁= ( V_T1, V_N1, R₁, S₁ ) и множество R₁ - это группа модифицированных правил

S ® aS ½ bC ½ dC

C ® bC ½ cC ½ û ë F,

где F - заключительный нетерминал, и А-язык L₂ определяется А-грамматикой

G₂=(V_T2, V_N2, R₂, S₂) и

Выполним формальную процедуру операции пересечения.

Определим грамматику G=( V_N, V_T, R, < 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>.

То есть операция пересечения L=L₁Ç L₂ определяется следующим образом:

G=< V_T1Ç V_T2, V_N={< A₁A₂>, A₁Î V_N1, A₂Î V_N2}, < S₁S₂>, R={< AB> ®a< CD>, если в исходной грамматике G₁ присутствует правило вида A®aC: A, CÎ V_N1, B®aD, B, DÎ V_N2} >.

В результате такого построения получается язык, включающий множество цепочек, принадлежащих языку L₁ и L₂. Действительно:

а) если jÎ L₁, L₂ Þ существует вывод в L₁ и L₂ Þ в L₁: j=ab…f, значит

существует вывод S₁aA₁bB₁…fF₁ в G₁ и вывод в G₂: S₂aA₂bB₂…fF₂.

По построению, если существуют такие правила вывода, то в L появится правило вида < S₁S₂> a< A₁A₂> …f< F₁F₂>.

Значит, если есть такой вывод, то цепочка j принадлежит L.

б) Проводя аналогичные рассуждения в обратном порядке, получим, что любая цепочка, принадлежащая языку L, принадлежит языкам L₁ и L₂. †

Рассмотрим еще один пример:

В результате выполнения операции пересечения получим:

– тупик