Чего автомат не может: язык aⁿbⁿ и довод о двух неразличимых началах

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

Как думаешь, хватит ли миллиона состояний

Нужно проверять строки вида «n открывающих скобок, затем n закрывающих». Автомат с пятью состояниями явно не справится с глубиной в сто. Но состояний можно взять сколько угодно.

Ответь себе до чтения: существует ли автомат - пусть с миллионом, пусть с триллионом состояний, - который принимает такие строки для любого n и ни одной лишней? Нет. Какой бы автомат ни предъявили, найдётся строка, на которой он ошибётся, - не длиннее удвоенного числа его состояний.

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

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

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

Механизм: два начала, одно состояние

Пусть какой-то ДКА с k состояниями принимает язык aⁿbⁿ - все строки из n букв a и следом n букв b, и только их.

Скормим ему по очереди начала ε, a, aa, …, aᵏ - это k + 1 строка (ε здесь - сама пустая строка, и она тоже в языке: ноль букв a и ноль букв b). Состояний k, строк больше, чем состояний, - значит, по принципу Дирихле какие-то две из этих строк, aⁱ и aʲ с i ≠ j, приводят автомат в одно и то же состояние q.

Теперь допишем к обеим хвост bⁱ. Автомат детерминирован: из состояния q по одному и тому же хвосту он придёт в одно и то же состояние. Значит, строки aⁱbⁱ и aʲbⁱ он либо обе примет, либо обе отвергнет. Но первая лежит в языке, а вторая нет. Противоречие с тем, что автомат принимает язык.

aⁱ ──► состояние q ──► bⁱ ──► ?        одно и то же «?» для обеих строк
aʲ ──► состояние q ──► bⁱ ──► ?        а ответы должны быть разными

Довод обобщается. Два начала различимы для языка, если к ним можно дописать один и тот же хвост так, что одна получившаяся строка в языке, а другая нет. Различимые начала обязаны приводить автомат в разные состояния. Если у языка бесконечно много попарно различимых начал, конечного числа состояний не хватит никакого - язык не регулярен.

Рядом с этим доводом стоит другой, лемма о накачке; он выводится из того же повтора состояния: в длинной строке регулярного языка путь автомата дважды проходит через одно состояние, и кусок строки между этими проходами можно повторить любое число раз или выбросить - автомат не заметит разницы. В строке aᵏbᵏ повтор состояния случается уже на первых k символах: путь по ним проходит k + 1 состояние, а разных всего k. Эти символы - одни буквы a, поэтому кусок состоит из букв a, и его повтор нарушает равенство.

Правило

Если для языка существует бесконечно много начал, никакие два из которых нельзя заменить друг другом (для каждой пары найдётся хвост, с которым одна строка в языке, а другая нет), то язык не регулярен. Так доказывается нерегулярность aⁿbⁿ, правильных скобочных записей, палиндромов и языка «букв a и b поровну». Дополнение регулярного языка (все строки над тем же алфавитом, которые в него не входят), пересечение и объединение двух регулярных языков снова регулярны - говорят, что регулярные языки замкнуты относительно этих операций. Для пересечения строится автомат, состояния которого - пары состояний двух автоматов.

Разбор: автомат, который старается, и строка, которая его ломает

Автомат «с пальцами»: состояния от 0 до k считают буквы a и на k останавливаются; состояние k + j помнит, что осталось дождаться j букв b; есть одно принимающее состояние и ловушка. Он честно принимает aⁿbⁿ для n от 1 до k; пустую строку, случай n = 0, он ради простоты отвергает, и на довод это не влияет. Вторая часть программы делает то, что сказано в механизме: ищет два начала с одним состоянием и предъявляет строку, на которой автомат ошибается.

def sdelat_avtomat(k):
    # 0..k - сколько букв a прочитано (не больше k);
    # k + j - ждём ещё j букв b; 2k - принимающее, 2k + 1 - ловушка
    prinyato = 2 * k
    lovushka = 2 * k + 1
    a = [lovushka] * (2 * k + 2)
    b = [lovushka] * (2 * k + 2)
    for q in range(k):
        a[q] = q + 1
    a[k] = k
    b[1] = prinyato
    for q in range(2, k + 1):
        b[q] = k + q - 1
    for j in range(1, k):
        if j == 1:
            b[k + j] = prinyato
        else:
            b[k + j] = k + j - 1
    return [a, b]

def konec(avtomat, stroka):
    q = 0
    for simvol in stroka:
        if simvol == "a":
            q = avtomat[0][q]
        else:
            q = avtomat[1][q]
    return q

k = 4
avtomat = sdelat_avtomat(k)
prinyato = 2 * k
otvety = []
for stroka in ["ab", "aabb", "aaabbb", "aaaabbbb",
               "aab", "abb", "aaaa", "ba"]:
    otvety.append(konec(avtomat, stroka) == prinyato)
print(otvety)

videl = {}
for i in range(2 * k + 3):
    q = konec(avtomat, "a" * i)
    if q in videl:
        j = videl[q]
        print(j, i, q)
        vernaya = konec(avtomat, "a" * j + "b" * j) == prinyato
        lishnyaya = konec(avtomat, "a" * i + "b" * j) == prinyato
        print(vernaya, lishnyaya)
        break
    videl[q] = i

[True, True, True, True, False, False, False, False]
4 5 4
True True

Первая строка вывода: автомат правильно принимает ab, aabb, aaabbb и aaaabbbb и отвергает aab, abb, aaaa и ba. Вторая - найденная пара: начала aaaa и aaaaa приводят в одно состояние 4. В программе j - начало, найденное раньше, i - найденное позже, а хвост - j букв b: буквы стоят наоборот по сравнению с механизмом, довод тот же. Третья: строка a⁴b⁴ принята - и строка a⁵b⁴ принята тоже, хотя букв a в ней на одну больше.

Вторая часть программы не пользуется устройством автомата: ей нужны только таблица, начальное состояние и принимающее. Она перебирает начала, пока состояние не повторится, - а повториться оно обязано не позже чем через число состояний шагов. Увеличение k отодвигает ошибку, но не убирает её.

Разбор: что требует счёта, а что только притворяется

Языки, которые отпадают тем же доводом:

правильные скобочные записи   начала (, ((, (((, … различимы:
                              к каждому подходит своё число )
палиндромы                    начала a, aa, aaa, … различимы хвостом b
                              и тем же числом букв a
«a, потом b, столько же a»    те же начала и те же хвосты: это язык
                              прошлого урока, шаблон (a*)b\1
букв a и b поровну            начала a, aa, aaa, … различимы хвостом
                              из нужного числа b

А вот языки, которые похожи на счёт, но регулярны:

чётное число букв a             остаток от деления на 2:    2 состояния
длина строки кратна трём        остаток от деления на 3:    3 состояния
скобки с глубиной не больше 5   глубина от 0 до 5 и ловушка: 7 состояний
aⁿbⁿ при n не больше 100        конечный язык, а конечный язык всегда
                                регулярен: начал у его строк конечное
                                число, и автомат помнит начало целиком
сначала буквы a, потом буквы b  a*b*: число букв не сравнивается

Граница проходит не между «простым» и «сложным» и не между конечным и бесконечным языком - a* бесконечен и регулярен. Она проходит между «достаточно помнить одно из конечного числа значений» и «нужно помнить неограниченное число».

Последний приём - замкнутость. Если поменять местами принимающие и непринимающие состояния ДКА, получится автомат для дополнения языка. Если запустить два автомата одновременно - состоянием считать пару их состояний, - получится автомат для пересечения: он принимает, когда принимают оба. У автоматов с p и q состояниями в произведении p · q состояний. Этим пользуются для доказательств: язык «букв a и b поровну» в пересечении с регулярным a*b* даёт aⁿbⁿ, и если бы первый был регулярен, регулярным оказалось бы и пересечение, то есть aⁿbⁿ.

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

Вложенные структуры разбирают автоматом. Скобки, теги, блоки begin … end произвольной глубины - это aⁿbⁿ в другой одежде. Регулярное выражение для них работает до глубины, на которую рассчитано, и ошибается молча на следующей.

«Язык бесконечен, значит не регулярен». Нерегулярность - не про размер языка, а про то, сколько нужно помнить. Все строки из букв a и b образуют бесконечный язык с автоматом из одного состояния.

Лемму о накачке применяют в обратную сторону. Она говорит, что строки регулярного языка накачиваются. Из того, что строки какого-то языка накачиваются, его регулярность не следует.

«У настоящего компьютера память конечна, значит он конечный автомат». Формально да: состояний у него 2 в степени числа битов памяти. Но это число больше числа атомов во Вселенной уже для килобайта, и рассуждение «состояния когда-нибудь повторятся» ничего практического не даёт. Модель выбирают по тому, что она помогает понять, поэтому для программ берут модель с неограниченной памятью - она появится в третьей главе раздела.

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

Выбор инструмента. Задача про формат без вложенности - дата, номер, строка журнала - решается автоматом или регулярным выражением. Задача с вложенностью - выражение со скобками, JSON, язык разметки - требует стека, и следующая глава показывает модель, в которой он есть.

Проверка свойств автоматов. Для конечных автоматов разрешимо тоРазбирается в разделе 21, глава «Машина Тьюринга и что считается вычислением»: Универсальная машина: программа как данные, разрешимое и распознаваемое, что для программ неразрешимо: пуст ли язык (достижимо ли принимающее состояние - обход графа), одинаковы ли два автомата (пуст ли язык «принимает ровно один из двух» - произведение и обход). Поэтому протоколы и контроллеры стараются описывать автоматами: их можно проверить целиком, а не тестами.

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

Теперь сам

1. У автомата семь состояний. Среди каких начал наверняка найдутся два, приводящие его в одно состояние?
2. Регулярен ли язык «строки, длина которых кратна трём»? Сколько состояний нужно?
3. Регулярен ли язык «сначала сколько-то букв a, потом сколько-то букв b», без условия на количества?
4. Регулярен ли язык aⁿbⁿ при n не больше 100?
5. Один автомат проверяет делимость двоичного числа на три, другой - чётность числа единиц. Сколько состояний у автомата для языка «делится на три и единиц чётное число»?