Что можно решить про автоматы и грамматики: принадлежность, пустота, равенство

Если ты объяснишь, почему равенство двух конечных автоматов проверяется за конечное время, хотя строк бесконечно много, найдёшь алгоритмом пустоту языка грамматики и назовёшь вопрос, разрешимый для автоматов и неразрешимый для грамматик, - листай до «Теперь сам».

Как думаешь, сколько строк нужно проверить

Есть два конечных автомата, по тысяче состояний в каждом: старая версия проверки формата и новая, переписанная. Нужно убедиться, что они принимают один и тот же язык.

Ответь себе до чтения: сколько строк придётся подать обоим, чтобы быть уверенным? Строк бесконечно много, и перебрать их нельзя. Но перебирать и не нужно. Если подавать обоим автоматам одни и те же символы и следить за парой их состояний, то разных пар не больше миллиона. Обойдя все достижимые пары, мы узнаём всё: либо нашлась пара, где один автомат принимает, а другой нет, либо такой пары нет вообще. Миллион шагов вместо бесконечного перебора - и не «скорее всего равны», а доказано.

На что это похоже

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

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

Механизм: вопрос как язык и три вопроса про автоматы

Вопрос «обладает ли объект свойством» превращается в язык: множество описаний объектов, у которых свойство есть. Вопрос разрешим, если разрешим этот язык, то есть существует алгоритм, который на любом описании останавливается с верным ответом.

Принадлежность. Дан ДКА и строка; принимает ли он её? Алгоритм: выполнить автомат. Он делает ровно столько шагов, сколько символов в строке, и всегда останавливается. Для НКА - моделирование множеством состояний из первой главы.

Пустота. Дан ДКА; принимает ли он хоть одну строку? Автомат - граф: состояния - вершины, переходы - рёбра. Язык непуст тогда и только тогда, когда из начального состояния достижимо хотя бы одно принимающее. Обход графа в ширину отвечает за время, пропорциональное числу переходов.

Равенство. Даны два ДКА; одинаковы ли их языки? Строим автомат-произведение из первой главы: его состояния - пары состояний, по символу обе половины пары делают свой переход. Назовём пару плохой, если ровно один из двух автоматов в ней принимает. Языки различны тогда и только тогда, когда из начальной пары достижима плохая. Снова обход графа, только граф состоит из пар. Путь до плохой пары - строка, на которой автоматы отвечают по-разному; обход в ширину находит кратчайшую. По сути это проверка пустоты: спрашивается, пуст ли язык автомата-произведения, у которого принимающими объявлены плохие пары.

Пустота - частный случай равенства: язык пуст, если автомат равен автомату, который ничего не принимает.

Грамматики. Для КС-грамматик принадлежность решает алгоритм CYK из главы о грамматиках: таблица по кускам строки. Пустота решается пометкой: нетерминал назовём порождающим, если из него выводится хоть одна строка терминалов. Сначала помечаем нетерминалы, у которых есть правило без нетерминалов справа; затем - те, у которых есть правило, где все нетерминалы уже помечены; повторяем, пока пометки появляются. Язык непуст, если помечен начальный нетерминал.

А равенство языков двух грамматик неразрешимо: алгоритма нет и не будет. Доказательство опирается на следующую главу; здесь важна картина целиком.

вопрос                 ДКА           КС-грамматика    машина Тьюринга
принимает ли строку    да            да, CYK          нет
пуст ли язык           да, обход     да, пометка      нет
равны ли два языка     да, пары      нет              нет

Правило

Для конечных автоматов разрешимы принадлежность, пустота и равенство языков: первая - выполнением, вторая - обходом графа состояний, третья - обходом графа пар состояний. Для КС-грамматик разрешимы принадлежность и пустота, равенство неразрешимо. Чем сильнее модель, тем меньше вопросов о ней разрешимо.

Разбор: два автомата и кратчайшая строка, которая их различает

Автомат задан таблицей: строка таблицы - состояние, в ней переходы по 0 и по 1. Функция sravnit обходит пары состояний в ширину. Вместе с парой в очереди лежит строка, которая в неё привела. Множество videli хранит номера уже встреченных пар: пара состояний (x, y) записана одним числом x · len(b) + y, как номер клетки в таблице, - разным парам достаются разные числа. Возвращается вердикт, строка-свидетель и число пар, встреченных к моменту ответа. Аргументы prin_a и prin_b - списки принимающих состояний; начальным у обоих автоматов считается состояние 0, поэтому обход начинается с пары (0, 0).

def sravnit(a, prin_a, b, prin_b):
    ochered = [[0, 0, ""]]
    videli = {0}
    i = 0
    while i < len(ochered):
        para = ochered[i]
        i = i + 1
        if (para[0] in prin_a) != (para[1] in prin_b):
            return ["разные", para[2], len(videli)]
        for bit in [0, 1]:
            x = a[para[0]][bit]
            y = b[para[1]][bit]
            if x * len(b) + y not in videli:
                videli.add(x * len(b) + y)
                ochered.append([x, y, para[2] + str(bit)])
    return ["равны", "", len(videli)]

na_tri = [[0, 1], [2, 0], [1, 2]]
na_shest = []
for r in range(6):
    na_shest.append([2 * r % 6, (2 * r + 1) % 6])
print(sravnit(na_tri, [0], na_shest, [0, 3]))
s_oshibkoj = []
for r in range(6):
    s_oshibkoj.append([2 * r % 6, (2 * r + 1) % 6])
s_oshibkoj[5][1] = 4
print(sravnit(na_tri, [0], s_oshibkoj, [0, 3]))
chyotnost = [[0, 1], [1, 0]]
print(sravnit(na_tri, [0], chyotnost, [0]))
nichego = [[0, 0]]
print(sravnit(s_oshibkoj, [0, 3], nichego, []))
print(sravnit([[1, 1], [1, 1], [2, 2]], [2], nichego, []))

['равны', '', 6]
['разные', '10111', 10]
['разные', '101', 4]
['разные', '', 1]
['равны', '', 2]

na_tri - автомат из первой главы: делимость двоичного числа на три, три состояния. na_shest считает остаток от деления на шесть и принимает остатки 0 и 3 - то же свойство, записанное шестью состояниями. Первая строка вывода: равны, и для этого хватило шести пар из восемнадцати возможных.

В s_oshibkoj испорчен один переход: из состояния 5 по единице автомат идёт в 4 вместо 5. Алгоритм нашёл кратчайшую строку, на которой это заметно: 10111, число 23. На три оно не делится, а испорченный автомат его принимает. Все строки короче пяти символов оба автомата оценивают одинаково - тесты на коротких строках ошибку бы не показали.

Третья строка: делимость на три и чётность числа единиц расходятся на 101. Четвёртая и пятая - пустота через равенство. Испорченный автомат отличается от пустого уже на пустой строке: начальное состояние принимающее. А у автомата из последней строки принимающее состояние 2 есть, но оно недостижимо, и его язык пуст.

Разбор: пуста ли грамматика

Функция porozhdayushchie выполняет пометку: проходит по правилам, пока удаётся пометить что-то новое. Нетерминалы - ключи словаря, всё остальное в правых частях - терминалы.

def porozhdayushchie(pravila):
    horoshie = set()
    izmenilos = True
    while izmenilos:
        izmenilos = False
        for golova in pravila:
            if golova in horoshie:
                continue
            for pravaya in pravila[golova]:
                goditsya = True
                for simvol in pravaya:
                    if simvol in pravila and simvol not in horoshie:
                        goditsya = False
                if goditsya and golova not in horoshie:
                    horoshie.add(golova)
                    izmenilos = True
    return sorted(horoshie)

pervaya = {"S": ["AB", "aC"], "A": ["aA", "Ab"],
           "B": ["b", "BB"], "C": ["Sc", "c"]}
vtoraya = {"S": ["AB", "aA"], "A": ["aA", "Ab"], "B": ["b", "BB"]}
tretya = {"S": ["(S)S", ""]}
for g in [pervaya, vtoraya, tretya]:
    h = porozhdayushchie(g)
    print(h, "S" in h)

['B', 'C', 'S'] True
['B'] False
['S'] True

В первой грамматике нетерминал A бесполезен: оба его правила содержат A, и вывод из него никогда не закончится. Но S порождающий - через правило S → aC. Во второй грамматике оба правила S требуют A, поэтому S не помечен: правил много, а язык пуст. Третья - скобки; S помечен сразу, благодаря правилу с пустой правой частью.

Внешний цикл повторяется, пока пометки появляются, а пометить каждый нетерминал можно один раз: проходов не больше, чем нетерминалов, плюс один. Алгоритм всегда останавливается - это и делает вопрос разрешимым.

Почему тот же приём не решает равенство грамматик? У автоматов равенство свелось к пустоте языка произведения: «есть ли строка, которую принимает ровно один». Для грамматик это потребовало бы пересечения и дополнения, а КС-языки относительно них не замкнуты: пересечение двух КС-языков или дополнение КС-языка может уже не быть КС-языком, и грамматики для него не существует. Конструкции, на которой держался алгоритм, здесь нет.

Что ломается без этого

Равенство проверяют тестами. Тесты показывают расхождение, если оно попалось, и ничего не доказывают, если не попалось. Испорченный автомат выше совпадает с правильным на всех строках короче пяти символов.

«Строк бесконечно много, значит проверить нельзя». Можно, когда у объекта конечное число состояний: бесконечное множество строк проходит через конечное множество пар.

Приём переносят на более сильную модель. Для грамматик равенство неразрешимо, для программ неразрешимо почти всё. Инструмент, обещающий «сравнить две программы на равенство поведения», либо работает на узком классе программ, либо иногда отвечает «не знаю».

Бесполезные правила остаются в грамматике. Нетерминал, из которого ничего не выводится, не меняет язык, но сбивает читателя, а рекурсивный спуск по правилу вроде A → aA не завершится никогда. Пометка находит такие за один прогон.

Зачем это в работе

Проверка переписанного. Регулярное выражение без обратных ссылок упростили, таблицу протокола пересобрали, фильтр оптимизировали: старый и новый вариант переводят в автоматы и сравнивают целиком. Ответ - либо «равны», либо конкретная строка, на которой они расходятся.

Проверка моделей. Протокол или контроллер описывают конечным автоматом, а требование - «плохое состояние недостижимо» - проверяют обходом. Это работает ровно потому, что пустота для автоматов разрешима.

Правило наименьшей силы. Языки конфигурации, фильтров и запросов часто намеренно делают слабее тьюринг-полных: без неограниченных циклов и рекурсии. Плата - выразительность, выигрыш - программу можно проверить до запуска. Так устроена проверка программ eBPF - небольших программ, которые администратор загружает прямо в ядро Linux, например для разбора сетевых пакетов: загружается только то, для чего проверяльщик сумел доказать завершение и безопасность обращений к памяти.

Теперь сам

1. У одного автомата 20 состояний, у другого 30. Сколько пар состояний в худшем случае обойдёт проверка равенства?
2. Языки двух автоматов различаются. Что можно сказать о длине кратчайшей строки, на которой они расходятся?
3. Грамматика: S → aSb | A, A → aA. Пуст ли её язык?
4. Как проверить, что язык одного автомата целиком содержится в языке другого?
5. Какой из вопросов разрешим для ДКА и неразрешим для КС-грамматик?