Недетерминизм: автомат, который угадывает, и его цена

Если ты смоделируешь НКА множеством состояний, построишь по нему ДКА и объяснишь, откуда берётся 2ⁿ, - листай до «Теперь сам».

Как думаешь, можно ли узнать третий символ с конца, не зная, где конец

Автомат читает строку из нулей и единиц слева направо и должен принять её, если третий символ с конца - единица. Где конец строки, он узнаёт только тогда, когда строка кончилась.

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

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

Поиск выхода из лабиринта толпой. На каждой развилке группа делится и идёт во все коридоры сразу; в тупике часть группы просто исчезает. Развилка - это очередной символ строки, и считается только то, где люди стоят после последнего символа: выход найден, если в этот момент у выхода стоит хотя бы один человек.

Никто в толпе не угадывает правильный коридор. Угадывание - способ описать результат: «существует последовательность поворотов, ведущая к выходу». А способ проверить это - следить не за одним человеком, а за тем, в каких залах сейчас кто-нибудь есть.

Механизм: множество возможных состояний

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

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

Автомат для «третий символ с конца - единица»:

состояние   по 0    по 1      что означает
    0       {0}     {0, 1}    ждём; единица может оказаться той самой
    1       {2}     {2}       «та самая» единица только что прочитана
    2       {3}     {3}       после неё прошёл один символ
    3       -       -         прошло два; принимающее: здесь строка
                              должна кончиться, переходов нет

Развилка одна - в состоянии 0 по единице: остаться ждать или объявить эту единицу третьей с конца.

Моделирование. Будем хранить множество состояний, в которых автомат может находиться после прочитанной части строки. Сначала это {начальное} и всё, куда из него можно дойти ε-переходами. На каждый символ новое множество - объединение переходов из всех состояний текущего, снова пополненное ε-переходами. В конце строка принята, если в множестве есть принимающее состояние. Цена одного символа - не больше числа переходов автомата (у автомата с n состояниями их до n² на символ), и никакого перебора путей.

От НКА к ДКА. Множество возможных состояний ведёт себя как одно состояние обычного автомата: по нему и по символу следующее множество определено однозначно. Значит, можно построить ДКА, состояния которого - множества состояний НКА; начальное - множество из начального состояния НКА и всего, куда из него ведут ε-переходы, принимающие - те, что содержат принимающее состояние НКА. Это построение подмножеств. У НКА с n состояниями подмножеств 2ⁿ, и столько состояний может понадобиться ДКА в худшем случае; на деле строят только достижимые.

Отсюда главный вывод: языки, которые принимают НКА, - те же регулярные языки. Недетерминизм не расширяет класс, он только сокращает запись.

Правило

НКА принимает строку, если хотя бы один путь по его переходам, включая ε-переходы, прочитывает её и заканчивается в принимающем состоянии. Его моделируют множеством возможных состояний: работы на один символ - не больше, чем у автомата всего переходов. Построение подмножеств превращает НКА с n состояниями в равносильный ДКА не более чем с 2ⁿ состояниями. НКА и ДКА принимают один и тот же класс языков - регулярные.

Разбор: моделирование масками

Множество состояний удобно хранить числом, как в разделе про биты: бит q равен единице, если состояние q возможно. perehody[q][bit] - маска состояний, куда можно попасть из q по символу bit. Функция shag объединяет маски переходов по всем единичным битам текущего множества. Порядок действий в Python: сдвиг выполняется раньше &, а & раньше сравнения, поэтому mnozhestvo >> k & 1 == 1 - это ((mnozhestvo >> k) & 1) == 1.

def nka_tretij_s_konca(k):
    perehody = []
    for q in range(k + 1):
        perehody.append([0, 0])
    perehody[0][0] = 1
    perehody[0][1] = 1 | 2
    for q in range(1, k):
        perehody[q][0] = 1 << (q + 1)
        perehody[q][1] = 1 << (q + 1)
    return perehody

def shag(perehody, mnozhestvo, bit):
    novoe = 0
    q = 0
    while mnozhestvo >> q:
        if mnozhestvo >> q & 1:
            novoe = novoe | perehody[q][bit]
        q = q + 1
    return novoe

def prinimaet(perehody, k, stroka):
    mnozhestvo = 1
    for simvol in stroka:
        mnozhestvo = shag(perehody, mnozhestvo, int(simvol))
    return mnozhestvo >> k & 1 == 1

nka = nka_tretij_s_konca(3)
for stroka in ["100", "0100", "1011", "0011", "11"]:
    print(stroka, prinimaet(nka, 3, stroka))

100 True
0100 True
1011 False
0011 False
11 False

Строка 0100: множества идут так - {0}, по нулю {0}, по единице {0, 1}, по нулю {0, 2}, по нулю {0, 3}. В конце в множестве есть состояние 3 - принята. Строка 1011: после неё множество {0, 1, 2}, состояния 3 в нём нет; третий символ с конца - ноль. Строка 11 слишком коротка, и ни один путь не успевает дойти до состояния 3.

Функция построена для любого k: тот же код даёт автомат для «k-й символ с конца - единица» с k + 1 состоянием.

Разбор: сколько состояний получится у ДКА

Построение подмножеств обходом в ширину: начинаем с множества {0}, для каждого найденного множества вычисляем соседей по нулю и по единице и добавляем новые. Словарь nomer хранит уже найденные множества.

def nka_s_konca(k):
    perehody = []
    for q in range(k + 1):
        perehody.append([0, 0])
    perehody[0][0] = 1
    perehody[0][1] = 1 | 2
    for q in range(1, k):
        perehody[q][0] = 1 << (q + 1)
        perehody[q][1] = 1 << (q + 1)
    return perehody

def shag(perehody, mnozhestvo, bit):
    novoe = 0
    q = 0
    while mnozhestvo >> q:
        if mnozhestvo >> q & 1:
            novoe = novoe | perehody[q][bit]
        q = q + 1
    return novoe

def sostoyanij_dka(perehody):
    nomer = {1: 0}
    ochered = [1]
    i = 0
    while i < len(ochered):
        m = ochered[i]
        i = i + 1
        for bit in [0, 1]:
            sosed = shag(perehody, m, bit)
            if sosed not in nomer:
                nomer[sosed] = len(nomer)
                ochered.append(sosed)
    return len(nomer)

for k in [1, 2, 3, 4, 5, 6, 7, 8]:
    print(k, k + 1, sostoyanij_dka(nka_s_konca(k)))

1 2 2
2 3 4
3 4 8
4 5 16
5 6 32
6 7 64
7 8 128
8 9 256

Столбцы: k, число состояний НКА и число достижимых состояний построенного ДКА. У НКА состояний k + 1, у ДКА - ровно 2ᵏ: на каждое добавленное состояние автомат удваивается. Всех подмножеств у k + 1 состояний вдвое больше, 2ᵏ⁺¹, но состояние 0 входит в каждое достижимое множество (из него по любому символу есть переход в него же), и свободны только остальные k.

Вот построенный ДКА для k = 2 целиком. У НКА состояния 0, 1, 2, принимающее - 2:

состояние ДКА    по нулю      по единице    принимающее
{0}              {0}          {0, 1}        нет
{0, 1}           {0, 2}       {0, 1, 2}     нет
{0, 2}           {0}          {0, 1}        да: в множестве есть 2
{0, 1, 2}        {0, 2}       {0, 1, 2}     да

И это не недостаток построения: меньше состояний у ДКА для этого языка быть не может. Возьмём две разные строки длины k. Они отличаются в какой-то позиции; допишем к обеим один и тот же хвост такой длины, чтобы эта позиция стала k-й с конца. Одна из получившихся строк в языке, другая нет. Если бы после исходных двух строк автомат стоял в одном состоянии, одинаковый хвост привёл бы его в одно и то же состояние, и ответ был бы одинаков. Значит, состояния были разные. Строк длины k всего 2ᵏ, и все они требуют разных состояний.

Граница вывода «недетерминизм ничего не добавляет» - он верен для конечных автоматов. У автоматов со стеком из следующей главы недетерминированный вариант строго сильнее. А для машин с неограниченной памятью вопрос, можно ли убрать угадывание, оставшись в пределах полиномиального времени, - это и есть задача о P и NPРазбирается в разделе 21, глава «P, NP, сведения и NP-полнота»: Класс NP: решение легко проверить, даже когда трудно найти, до которой дойдёт пятая глава. Экспонента в таблице выше - первая встреча с ценой отказа от угадывания. Здесь она доказана и касается размера автомата; в задаче о P и NP речь о времени работы, и ответ там неизвестен.

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

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

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

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

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

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

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

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

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

Теперь сам

1. Смоделируй автомат «третий с конца - единица» на строке 0110: выпиши множества после каждого символа.
2. У НКА десять состояний. Сколько состояний может оказаться у построенного по нему ДКА в худшем случае?
3. Сколько состояний у НКА и у наименьшего ДКА для языка «двадцатый символ с конца - единица»?
4. Есть два ДКА для языков A и B. Как одним ε-переходом на каждый собрать из них НКА для языка «строка лежит в A или в B»?
5. При моделировании множество возможных состояний стало пустым, а строка ещё не кончилась. Что это значит?