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

Рассмотрим пересечение двух регулярных языков. Здесь почти нечего делать, поскольку операции объединения, дополнения и пересечения не являются независимыми. Пересечение языков 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 обозначается w R. Таким образом, 0010R есть 0100, а R = . Обращение языка L, обозначаемое L R, состоит из всех цепочек, обратных цепочкам языка L. Например, если L = {001, 10, 111}, то L R = {100, 01, 111}.

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

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

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

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

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

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

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

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

Пример. (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]