Свойство замкнутости регулярных языков

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

1. Объединение.

2. Пересечение.

3. Дополнение.

4. Разность.

5. Обращение.

6. Итерация (звездочка).

7. Конкатенация.

8. Гомоморфизм (подстановка цепочек вместо символов языка).

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

Замкнутость относительно булевых операций

Сначала рассмотрим замкнутость для трех булевых операций: объединение, пересечение и дополнение.

1. Пусть L и M — языки в алфавите V. Тогда язык L U M содержит все цепочки, которые принадлежат хотя бы одному из языков L или M.

2. Пусть L и M — языки в алфавите V. Тогда язык L ∩ M содержит все цепочки, принадлежащие обоим языкам L и M.

3. Пусть L — некоторый язык в алфавите V. Тогда язык L , дополнение L, — это множество тех цепочек в алфавите V*, которые не принадлежат L.

При объединении или пересечении двух языков L и M может оказаться, что они определены в разных алфавитах. Например, возможен случай, когда L1 ⊆{a, b}, а L2 ⊆ {b, c, d}. Можно представить указанные выше языки L1 и L2 как языки в алфавите {a, b, c, d}. То, что ни одна цепочка языка L1 не содержит символов c или d, несущественно, как и то, что ни одна цепочка языка L2 не содержит a.

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

Замкнутость относительно объединения

Теорема. Если L и M — регулярные языки, то L U M также регулярен.

Доказательство. Поскольку языки L и M регулярны, им соответствуют некоторые регулярные выражения. Пусть L = L(R) и M = L(S). Тогда L U M = L(R + S) согласно определению операции + для регулярных выражений.

Замкнутость относительно регулярных операций

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

• если L и M — регулярные языки, то язык LM регулярен;

• если L — регулярный язык, то L* также регулярен.

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

Теорема для объединения языков легко доказывается с помощью регулярных выражений. Теперь рассмотрим дополнение. Знаете ли вы, как преобразовать регулярное выражение, чтобы оно определяло дополнение языка? Мы тоже не знаем.

Однако это выполнимо, можно начать с ДКА и построить ДКА, допускающий дополнение. Таким образом, начав с регулярного выражения для языка, можно найти выражение для его дополнения следующим образом.

1. Преобразовать регулярное выражение в -НКА.

2. Преобразовать -НКА в ДКА с помощью конструкции подмножеств.

3. Дополнить допускающие состояния этого ДКА.

4. Преобразовать полученный ДКА для дополнения обратно в регулярное выражение

Теорема Если L — регулярный язык в алфавите V, то язык ¯L = V* – L также регулярен.

Доказательство. Пусть L = L(A) для некоторого ДКА A = (Q, V,f, q0, F). Тогда = L(B), где B — это ДКА (Q, V, f, q0, Q – F), т.е. автоматы A и B одинаковы, за исключением того, что допускающие состояния автомата A стали не допускающими в B, и наоборот. Тогда w принадлежит L(B), если, и только если, f(q0, w) принадлежит Q – F, т.е. w не принадлежит L(A).

Заметим, что для приведенного выше доказательства важно, чтобы f(q0, w) всегда было некоторым состоянием. Это значит, что в автомате A все переходы определены.

Если бы некоторые переходы отсутствовали, то определенные цепочки не вели бы ни в допускающее, ни в недопускающее состояния автомата A, т.е. отсутствовали бы как в L(A), так и L(B). К счастью, ДКА определен так, что в любом состоянии у него есть переход по каждому символу алфавита V, так что каждая цепочка приводит в состояние либо из F, либо из Q – F.

Пример1. Пусть A — автомат, ДКА допускает те и только те цепочки символов 0 и 1, которые заканчиваются на 01. В терминах регулярных выражений L(A) = (0 + 1)*01. Таким образом, дополнение к L(A) содержит все те цепочки из нулей и единиц, которые не заканчиваются на 01. На рис. представлен автомат для {0, 1}* – L(A). Он совпадает с автоматом 1, за исключением того, что допускающие состояния стали не допускающими, а два не допускающих состояния стали допускающими.

Дополнение языка L.