Границы КС-языков и замкнутость

КС-языки мощнее регулярных, но и у них есть потолок. И ведут они себя капризнее: некоторые операции выводят за пределы класса.

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

Что замкнуто, а что нет

Хорошие новости: объединение L∪M, конкатенация L·M и звезда L^* двух КС-языков снова КС (строится прямо на грамматиках: добавить правило S → S₁ | S₂ для объединения и т.п.). Плохие новости: пересечение и дополнение КС-языков могут не быть КС. Это резкий контраст с регулярными, где замкнуто всё.

Классический пример незамкнутости пересечения. Пусть L₁ = {aⁿbⁿc^m} и L₂ = {a^mbⁿcⁿ} — оба КС (каждый сравнивает только две буквы, со стеком справляется). Но их пересечение:

L1 ∩ L2 = { a^n b^n c^m } ∩ { a^m b^n c^n }
        = { a^n b^n c^n }   ← равны все три!
        = НЕ КС-язык (доказали леммой о накачке)

Пересечение двух КС-языков дало aⁿbⁿcⁿ, который не КС. Значит, КС-языки не замкнуты относительно пересечения. Через де Моргана отсюда следует и незамкнутость относительно дополнения (иначе пересечение получалось бы из объединения и дополнений).

Полезное исключение: пересечение с регулярным

Есть важная лазейка: пересечение КС-языка с регулярным языком — снова КС. Это очень практично: можно «отфильтровать» КС-язык регулярным условием, оставаясь в классе. Конструкция — произведение PDA и конечного автомата (стек берётся от PDA, состояния — пара). Покажем идею: проверяем строки на КС-свойство (баланс ab) И регулярное (оканчивается на c).

def balanced_ab(s):              # КС: число a == число b в порядке a..b
    depth = 0
    for ch in s:
        if ch == "a": depth += 1
        elif ch == "b":
            depth -= 1
            if depth < 0: return False
        # c игнорируем для баланса
    return depth == 0

def ends_with_c(s):              # регулярное условие
    return s.endswith("c")

# пересечение: КС ∩ регулярный = снова КС
for w in ["abc", "aabbc", "abcc", "ab", "aabb"]:
    res = balanced_ab(w) and ends_with_c(w)
    print(f"{w:>6}: КС∩рег = {res}")

Вывод:

   abc: КС∩рег = True
 aabbc: КС∩рег = True
  abcc: КС∩рег = True
    ab: КС∩рег = False
  aabb: КС∩рег = False

«ab» сбалансирована, но не оканчивается на c — отсеяна регулярным условием. Класс КС при этом не покинут.

Верхняя граница: что дальше

За КС-языками идут контекстно-зависимые (тип 1): им уже доступен aⁿbⁿcⁿ и многое другое. Их распознаёт линейно-ограниченный автомат — машина Тьюринга с лентой, ограниченной длиной входа. Ещё выше — тип 0, рекурсивно-перечислимые языки и полная машина Тьюринга. Так мы подходим к вершине иерархии Хомского и к следующему разделу про вычислимость.

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

Почему регулярные замкнуты относительно всего, а КС — нет? Дело в детерминизации. Для регулярных мы умеем строить ДКА и инвертировать его (дополнение). Для КС детерминированные PDA слабее недетерминированных, и инверсия не работает — нет аналога чистой детерминизации. Стек, в отличие от конечной памяти, нельзя «обратить» так же легко. Это глубокая причина капризности КС-класса.

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

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

Забыть про лазейку с регулярными. КС ∩ регулярный = КС — это работает и очень полезно на практике (фильтрация).

Считать aⁿbⁿcⁿ вообще нераспознаваемым. Он не КС, но контекстно-зависим и легко распознаётся машиной Тьюринга — просто требует памяти мощнее стека.

Итог

КС-языки замкнуты относительно объединения, конкатенации и звезды.
НЕ замкнуты относительно пересечения и дополнения: L₁∩L₂ может дать не-КС aⁿbⁿcⁿ.
Лазейка: пересечение КС-языка с регулярным снова КС (произведение PDA и автомата).
Выше КС — контекстно-зависимые языки (тип 1, ЛО-автомат) и далее машина Тьюринга.