Замкнутость регулярных языков

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

Замкнутость класса относительно операции означает: результат операции над языками класса снова принадлежит этому классу.

Какие операции сохраняют регулярность

Регулярные языки замкнуты относительно широкого набора операций: объединение, конкатенация, звезда Клини (это прямо из определения регулярных выражений), а также дополнение, пересечение и разность. Эти свойства — не абстрактная роскошь: они дают мощный практический приём. Чтобы доказать регулярность сложного языка, достаточно собрать его из простых регулярными операциями. А чтобы доказать не-регулярность — наоборот, использовать замкнутость «от противного» (если бы L был регулярен, то и некий L', полученный операциями, был бы регулярен, но он явно нет).

Дополнение: переверни принимающие

Дополнение языка L — это все строки, не входящие в L. Для ДКА конструкция тривиальна и красива: возьмите полный ДКА для L и поменяйте местами принимающие и непринимающие состояния. Что раньше принималось — теперь отвергается, и наоборот. Важно: ДКА должен быть полным (переход определён для каждого символа), иначе строки, на которых автомат «застревал», потеряются.

L: чётное число единиц       ¬L: нечётное число единиц

  ──>((q0)) ⇄ (q1)            ──>(q0) ⇄ ((q1))
        1                          1
  принимающее: q0            принимающее: q1  (перевернули!)

Пересечение: произведение автоматов

Пересечение L∩M строится декартовым произведением двух ДКА: новое состояние — пара (состояние первого, состояние второго), оба автомата читают вход синхронно. Принимающее — пара, где оба компонента принимающие. Реализуем: пересечём «чётное число единиц» и «длина кратна 2».

# A: чётное число единиц     B: чётная длина
A = {("a0","0"):"a0", ("a0","1"):"a1", ("a1","0"):"a1", ("a1","1"):"a0"}
B = {("b0","0"):"b1", ("b0","1"):"b1", ("b1","0"):"b0", ("b1","1"):"b0"}
Aacc, Bacc = {"a0"}, {"b0"}

def run_product(w):
    sa, sb = "a0", "b0"
    for ch in w:
        sa, sb = A[(sa, ch)], B[(sb, ch)]
    return sa in Aacc and sb in Bacc   # оба принимают

for w in ["", "11", "1", "1010", "110"]:
    print(f"{w or 'ε':>5} -> {run_product(w)}")

Вывод:

    ε -> True
   11 -> True
    1 -> False
 1010 -> True
  110 -> False

«11» проходит (две единицы — чётно, длина 2 — чётна), «110» отвергнута (длина 3 нечётна). Пересечение реализовано без построения нового автомата явно — просто симулируем оба синхронно.

Как работает под капотом

Замкнутость относительно пересечения и дополнения легко выводится через объединение по закону де Моргана: L∩M = ¬(¬L ∪ ¬M). Раз есть дополнение и объединение, пересечение получается автоматически. Это показывает внутреннюю согласованность теории. Декартово произведение — самая полезная конструкция на практике: на нём строят верификацию. Свойство системы кодируют автоматом-«наблюдателем», поведение системы — другим автоматом, берут произведение и проверяют, достижимо ли «плохое» состояние. Если язык пересечения пуст — система безопасна.

Частые ошибки

Дополнять неполный ДКА. Перед инверсией принимающих состояний достройте ловушку для всех неопределённых переходов, иначе дополнение будет неверным.

Делать дополнение на НКА инверсией состояний. Так нельзя! Инверсия принимающих в НКА не даёт дополнение (из-за критерия «существует путь»). Сначала детерминизируйте, потом инвертируйте.

Считать, что замкнуто всё. Например, для регулярных всё хорошо, но КС-языки не замкнуты относительно пересечения и дополнения — об этом в шестом разделе.

Итог

Регулярные языки замкнуты относительно объединения, конкатенации, звезды, дополнения, пересечения и разности.
Дополнение: инверсия принимающих состояний полного ДКА (не НКА!).
Пересечение: декартово произведение автоматов, принимает, когда принимают оба.
Замкнутость — инструмент доказательств (и регулярности, и не-регулярности) и основа верификации.