Магазинный автомат: конечное управление и стек

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

Как думаешь, хватит ли счётчика

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

Ответь себе до чтения: если завести два счётчика, по одному на вид скобок, получится ли проверка? Строку ([)] два счётчика примут: каждого вида открыто и закрыто поровну, и ни один счётчик не уходит в минус. А запись неправильная. Недостаточно знать, сколько скобок открыто; нужно знать, какая открыта последней, а когда она закроется - какая была перед ней.

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

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

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

Механизм: шаг автомата со стеком

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

( состояние,  очередной символ строки,  символ на верхушке стека )
                         ↓
( новое состояние,  строка символов, которой заменяется верхушка )

Замена верхушки покрывает все три действия со стеком:

заменить A на пустую строку      снять верхушку
заменить A на A                  оставить стек как есть
заменить A на A и B              положить B поверх A

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

Автомат для aⁿbⁿ при n не меньше единицы (пустую строку он ради простоты не принимает). Символы стека - свой отдельный алфавит: здесь это $ и A, «прочитана одна буква a». Заглавная буква - не нетерминал из прошлого урока; можно было бы класть и саму a. Принимающее состояние - 1:

состояние 0, читаем a:   на верхушке $ или A  →  положить A, остаться в 0
состояние 0, читаем b:   на верхушке A        →  снять A, перейти в 1
состояние 1, читаем b:   на верхушке A        →  снять A, остаться в 1
всё остальное - перехода нет, строка отвергнута

Состояний два, и они помнят только одно: началась ли вторая половина. Количество букв a помнит стек. Конечное управление - состояния с таблицей переходов, то есть всё, кроме стека, - плюс неограниченная, но неудобная память: вот и вся модель.

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

Две теоремы, которые связывают автомат с прошлым уроком. Первая: по любой КС-грамматике строится недетерминированный магазинный автомат для того же языка, и по любому такому автомату - грамматика. Идея построения: автомат держит в стеке ещё не разобранный остаток вывода. Нетерминал на верхушке он заменяет правой частью одного из его правил - какого именно, угадывает, отсюда недетерминизм, - а терминал на верхушке сверяет с очередным символом строки и снимает. Правую часть кладут задом наперёд, чтобы её первый символ оказался на верхушке - в записи стека она справа. Для S → aSb | ε и строки ab стек проходит S, bSa, bS, b и пустеет. Грамматики и недетерминированные магазинные автоматы описывают один класс, контекстно-свободные языки. Вторая: детерминированные магазинные автоматы принимают строго меньший класс. Существуют КС-языки, для которых детерминированного автомата нет, и язык чётных палиндромов - один из них.

Правило

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

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

Таблица переходов - словарь: ключ склеен из состояния, символа строки и верхушки стека, значение - новое состояние и строка, заменяющая верхушку. Стек хранится строкой, верхушка - её последний символ. Функция zapusk возвращает ответ и наибольшую высоту стека за время работы. Принимающие состояния передаются строкой из их имён: "1" - одно состояние, "12" были бы два.

def zapusk(perehody, prinimayushchie, stroka):
    sostoyanie = "0"
    stek = "$"
    vysota = 1
    for simvol in stroka:
        klyuch = sostoyanie + simvol + stek[-1]
        if klyuch not in perehody:
            return [False, vysota]
        hod = perehody[klyuch]
        sostoyanie = hod[0]
        stek = stek[:-1] + hod[1]
        if len(stek) > vysota:
            vysota = len(stek)
    return [sostoyanie in prinimayushchie and stek == "$", vysota]

porovnu = {}
porovnu["0a$"] = ["0", "$A"]
porovnu["0aA"] = ["0", "AA"]
porovnu["0bA"] = ["1", ""]
porovnu["1bA"] = ["1", ""]
for stroka in ["ab", "aaabbb", "aabbb", "aab", "abab",
               "a" * 40 + "b" * 40]:
    print(zapusk(porovnu, "1", stroka))

skobki = {}
for verh in "$([":
    skobki["0(" + verh] = ["0", verh + "("]
    skobki["0[" + verh] = ["0", verh + "["]
skobki["0)("] = ["0", ""]
skobki["0]["] = ["0", ""]
for stroka in ["([])", "([)]", "(()", "[]()[()]", "]"]:
    print(stroka, zapusk(skobki, "0", stroka))

[True, 2]
[True, 4]
[False, 3]
[False, 3]
[False, 2]
[True, 41]
([]) [True, 3]
([)] [False, 3]
(() [False, 3]
[]()[()] [True, 3]
] [False, 1]

Первые шесть строк - автомат для aⁿbⁿ. Строка aabbb отвергнута: третью b встречает дно, а перехода для тройки «состояние 1, b, $» нет. Строка aab прочитана до конца, но в стеке осталась лишняя A. Строка abab отвергнута на второй a: в состоянии 1 буква a не разрешена. На сорока буквах a стек вырос до 41 символа - дно и сорок A; конечному автомату, который принимает aⁿbⁿ хотя бы до n = 40, понадобилось бы больше сорока состояний, а здесь их по-прежнему два.

Вторая половина - автомат для скобок двух видов, и у него одно состояние. Открывающая скобка кладётся в стек поверх чего угодно; закрывающая разрешена, только если на верхушке лежит открывающая того же вида. Строка ([)], которую принимали два счётчика, отвергнута на третьем символе: пришла ), а на верхушке [. Здесь стек нужен именно как стек: важен порядок, а не количество.

Разбор: палиндром и угаданная середина

Язык чётных палиндромов над {a, b}: строка, вторая половина которой - первая, прочитанная задом наперёд. План автомата: первую половину класть в стек, вторую сверять с верхушкой, снимая. Беда в том, что середина ничем не отмечена.

Недетерминированный автомат её угадывает: перед каждым символом у него есть переход без чтения из состояния «кладём» (в программе 0) в состояние «сверяем» (в программе 1). Таблицы здесь нет, переходы записаны прямо ветками if. Моделируем его так же, как НКА, - ведём список всех возможных конфигураций, только конфигурация теперь не состояние, а пара «состояние, содержимое стека». Начальных конфигураций две: «кладём» с пустым стеком и «сверяем» с пустым стеком - переход без чтения возможен ещё до первого символа, это догадка «середина в самом начале». Дно в этой программе не хранится: стек - строка Python, и его пустоту видно по длине.

def palindrom(stroka):
    konfiguracii = [[0, ""], [1, ""]]
    naibolshee = 2
    for simvol in stroka:
        novye = []
        for k in konfiguracii:
            if k[0] == 0:
                stek = k[1] + simvol
                novye.append([0, stek])
                novye.append([1, stek])
            elif len(k[1]) > 0 and k[1][-1] == simvol:
                novye.append([1, k[1][:-1]])
        konfiguracii = novye
        if len(konfiguracii) > naibolshee:
            naibolshee = len(konfiguracii)
    prinyata = False
    for k in konfiguracii:
        if k[0] == 1 and k[1] == "":
            prinyata = True
    return [prinyata, naibolshee]

for stroka in ["abba", "abab", "aabbaa", "aba"]:
    print(stroka, palindrom(stroka))
for n in [8, 16, 32, 64]:
    print(n, palindrom("a" * n), palindrom("ab" * (n // 2)))

abba [True, 3]
abab [False, 2]
aabbaa [True, 4]
aba [False, 2]
8 [True, 6] [False, 2]
16 [True, 10] [False, 2]
32 [True, 18] [False, 2]
64 [True, 34] [False, 2]

Каждая строка вывода - ответ и наибольшее число конфигураций, которые пришлось держать одновременно. В последних четырёх строках три поля: длина, результат для строки из одних a и результат для abab.... Конфигурация в состоянии 0 всегда одна: «середины ещё не было». Каждая конфигурация в состоянии 1 - одна догадка «середина была вот здесь», и живёт она, пока строка подтверждает её. На строке abab... догадки умирают сразу, и конфигураций две. На строке из одних букв a любая догадка правдоподобна, пока не кончится её стек, и конфигураций около n/2: 34 при длине 64.

Рост линейный, а не экспоненциальный - для этого автомата. Его стек определяется местом догадки, и догадок не больше, чем позиций. У произвольного магазинного автомата разных содержимых стека может быть экспоненциально много, и прямое слежение за конфигурациями перестаёт работать; общий способ разбора КС-языков устроен иначе и появится через два урока.

Важнее другое. У конечных автоматов множество возможных состояний само было состоянием нового автомата - так недетерминизм убирался. Здесь множество конфигураций не укладывается в один стек: n/2 разных стеков одним не заменить. И это не недостаток придумки: доказано, что детерминированного магазинного автомата для чётных палиндромов не существует. Если середину отметить особым символом - язык строк вида «слово, c, то же слово задом наперёд», - детерминированный автомат строится сразу.

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

Счётчик вместо стека. Работает, пока вид скобок один. Теги разметки, скобки трёх видов, блоки begin … end вперемешку с if … fi требуют помнить порядок открытия.

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

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

Стек принят за произвольную память. Автомат видит только верхушку. Язык aⁿbⁿcⁿ ему не по силам: сверяя буквы b с буквами a, он стирает счёт, и для букв c сравнивать уже не с чем. Доказательство - в последнем уроке главы.

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

Разборщики. Почти любой синтаксический анализатор - магазинный автомат: либо явный, с таблицей и стеком, либо скрытый в рекурсивных функциях, где стеком служит стек вызовов. Следующий урок строит второй вариант.

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

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

Теперь сам

1. Проведи автомат для aⁿbⁿ по строке aabb: выпиши состояние и стек после каждого символа.
2. Почему автомат для скобок отвергает строку (()?
3. Опиши словами магазинный автомат для языка «букв a столько же, сколько букв b, в любом порядке».
4. Сколько конфигураций придётся держать автомату для палиндромов на строке из ста букв a?
5. Какой из языков детерминированный: aⁿbⁿ, чётные палиндромы, палиндромы с отмеченной серединой?