Замкнутость относительно пересечения

Рассмотрим пересечение двух регулярных языков. Здесь почти нечего делать, поскольку операции объединения, дополнения и пересечения не являются независимыми. Пересечение языков L и M выражается через объединение и дополнение следующим тождеством.

Вообще, пересечение двух множеств — это множество элементов, не принадлежащих дополнениям каждого из них. Это замечание, записанное в виде равенства, представляет один из законов Де Моргана.

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

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

Автомат, имитирующий два других автомата и допускающий тогда и только тогда, когда допускают оба автомата

Теорема.Если L и M — регулярные языки, то язык L ∩M также регулярен. На рис., представлен автомат — произведение двух данных автоматов. Его состояния помеченыкак пары состояний исходных автоматов.

Легко доказать, что этот автомат допускает пересечение первых двух языков, т.е. те цепочки, которые содержат как 0, так и 1. Состояние pr представляет начальное условие, когда на вход автомата пока не поступили ни 0, ни 1. Состояние qr означает, что поступили только нули, а состояние ps — только единицы. Допускающее состояние qs представляет условие того, что на вход автомата поступили и нули, и единицы

Замкнутость относительно разности

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

Доказательство. Заметим, что . По теореме 4.5 регулярен язык , а по теореме 4.8 . Следовательно, язык L – M регулярен.[2]

Обращение

Обращением цепочки a1a2…an называется цепочка, записанная в обратном порядке,т.е. anan-1…a1. Обращение w обозначается wR. Таким образом, 0010R есть 0100, а R = . Обращение языка L, обозначаемое LR, состоит из всех цепочек, обратных цепочкам языка L. Например, если L = {001, 10, 111}, то LR = {100, 01, 111}.

Обращение является еще одной операцией, сохраняющей регулярность языков, т.е. если язык L регулярен, то LR также регулярен. Это легко доказать двумя способами, первый из которых основан на автоматах, а второй — на регулярных выражениях. Доказательство, основанное на автоматах, приводится неформально.

Затем приводится формальное доказательство, использующее регулярные выражения.

Если задан язык L, который есть L(A) для некоторого конечного автомата A, вероятно, с недетерминизмом и -переходами, то можно построить автомат для LR следующим образом.

1. Обратить все дуги на диаграмме переходов автомата A.

2. Сделать начальное состояние автомата A единственным допускающим состоянием нового автомата.

3. Создать новое начальное состояние p0 с -переходами во все допускающие состоя-

4. ния автомата A.

В результате получим автомат, имитирующий автомат A “в обратном порядке” и, следовательно, допускающий цепочку w тогда и только тогда, кода A допускает wR.

Пример. (0+1)0*

Гомоморфизмы

Гомоморфизм цепочек — это такая функция на множестве цепочек, которая подставляет определенную цепочку вместо каждого символа данной цепочки.

Пример 4.13.Функция h, определенная как h(0) = ab и h(1) = , является гомоморфизмом. В любой цепочке из символов 0 и 1 h заменяет все нули цепочкой ab, а все единицы — пустой цепочкой. Например, применяя h к цепочке 0011, получим abab. Формально, если h есть некоторый гомоморфизм на алфавите V, а w = a1a2…an — цепочка символов в V, то h(w) = h(a1)h(a2)…h(an). Таким образом, сначала h применяется к каждому символу цепочки w, а потом полученные цепочки символов соединяются в соответствующем порядке. Например, рассмотрим гомомор физм h из примера и цепочку w = 0011: h(w) = h(0)h(0)h(1)h(1) = (ab)(ab)()() = abab, что и утверждается в этом примере.

Гомоморфизм языка определяется с помощью его применения к каждой цепочке языка, т.е. если L — язык в алфавите V, а h — гомоморфизм на , то h(L) = {h(w) | w принадлежит L}. Рассмотрим язык L регулярного выражения 10*1, т.е. все цепочки, которые начинаются и заканчиваются единицей, а между ними содержат произвольное число нулей.

Пусть h — гомоморфизм из примера. Тогда h(L) — это язык выражения (ab)*. Объясняется это тем, что h исключает все единицы, заменяя их пустыми символами., а вместо каждого нуля подставляет цепочку ab. Идея применения гомоморфизма непосредственно к регулярному выражению используется для доказательства замкнутости регулярных языков относительно гомоморфизма.

Теорема Если L — регулярный язык в алфавите V, а h — гомоморфизм на V, то язык h(L) также регулярен.

Доказательство. Пусть L = L(R) для некоторого регулярного выражения R. Вообще, если E есть регулярное выражение с символами из алфавита V, то пусть h(E) — выражение, полученное в результате замены каждого символа a в выражении E цепочкой h(a).

Утверждается, что выражение h(R) определяет язык h(L).

Это легко доказать с помощью структурной индукции. Если применить гомоморфизм h к любому подвыражению E выражения R, то язык выражения h(E) совпадет с языком, полученным в результате применения этого гомоморфизма к языку L(E). Формально,

L(h(E)) = h(L(E)).

Базис.Если E есть пустой символ, то h(E) совпадает с E, поскольку h не влияет на цепочку или язык. Следовательно, L(h(E)) = L(E). В то же время, если E равно пустому символу то L(E) либо не содержит ни одной цепочки, либо состоит из цепочки без символов. Таким образом, в обоих случаях h(L(E)) = L(E). Из этого следует, что L(h(E)) = L(E) = h(L(E)).

Возможен еще один базисный вариант, когда E = aдля некоторого символа a . В этом случае L(E) = {a}, и h(L(E)) = {h(a)}. Выражение h(E) представляет собой цепочку символов h(a). Таким образом, язык L(h(E)) также совпадает с {h(a)}, и, следовательно,

L(h(E)) = h(L(E)).

Индукция.В зависимости от операции в регулярном выражении возможны три ситуации. Все они просты, поэтому обоснуем индукцию только для объединения, E = F + G.

Способ применения гомоморфизмов к регулярным выражениям гарантирует, что h(E) = h(F + G) = h(F) + h(G).

Нам также известно, что L(E) = L(F) U L(G) и L(h(E)) = L(h(F) + h(G)) = L(h(F)) U L(h(G)) (4.2) по определению операции + для регулярных выражений. Наконец, h(L(E)) = h(L(F) U L(G)) = h(L(F)) U h(L(G)), (4.3) поскольку h применяется к языку путем применения его к каждой цепочке этого языка по отдельности. По индуктивной гипотезе L(h(F)) = h(L(F)) и L(h(G)) = h(L(G)).

Таким образом, правые части выражений (4.2) и (4.3) эквивалентны, и, следовательно,

L(h(E)) = h(L(E)).

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

Итак, можно сделать вывод, что L(h(R)) действительно равняется h(L(R)), т.е. применение гомоморфизма к регулярному выражению языка L дает регулярное выражение, определяющее язык h(L).[3]

Обратный гомоморфизм

Гомоморфизм можно применять “назад”, и это также сохраняет регулярность языков.

Предположим, что h — гомоморфизм в алфавите V

Пусть L — язык в алфавите T. Тогда h-1(L), читаемое как“обратное h от L”, — это множество цепочек w из V*, для которых h(w) принадлежит L.

Пример 4.15.Пусть L — язык регулярного выражения (00+ 1)*, т.е. все цепочки из символов 0 и 1, в которых нули встречаются парами. Таким образом, цепочки 0010011 и 10000111 принадлежат L, а 000 и 10100 — нет.

Пусть h — такой гомоморфизм: h(a) = 01, h(b) = 10. Утверждается, что h–1(L) — это язык регулярного выражения (ba)*, т.е. все цепочки, в которых повторяются пары ba. Докажем, что h(w) принадлежит L тогда и только тогда, когда цепочка w имеет вид baba…ba.[8]

Достаточность. Предположим, что цепочка w состоит из n повторений ba для некоторого n ≥0. Заметим, что h(ba) = 1001, т.е. h(w) — это n повторений цепочки 1001. Поскольку цепочка 1001 построена из двух единиц и пары нулей, то она принадлежит языку L. Следовательно, цепочка, состоящая из любого числа повторений 1001, также образована единицами и парами нулей и принадлежит L. Таким образом, h(w) принадлежит L.

Необходимость. Теперь предположим, что h(w) принадлежит L, и покажем, что цепочка w имеет вид baba…ba. Существует четыре условия, при которых цепочка имеет другой вид. Покажем, что при выполнении любого из них h(w) не принадлежит L, т.е. докажем утверждение, противоположное тому, что нам нужно доказать.

1. Если w начинается символом а, то h(w) начинается с 01. Следовательно, она содержит отдельный 0 и поэтому не принадлежит L.

2. Если w заканчивается символом b, то в конце h(w) стоит 10, и опять-таки в цепочке h(w) есть изолированный 0.

3. Если в цепочке w дважды подряд встречается a, то h(w) содержит подцепочку 0101. Снова в w есть изолированный нуль.

4. Аналогично, если в w есть два символа b подряд, то h(w) содержит подцепочку 1010 с изолированным 0.[5]