Чего не умеет стек: язык aⁿbⁿcⁿ и лестница Хомского

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

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

Стек сверяет буквы a с буквами b: кладёт на каждую a, снимает на каждую b. Теперь после букв b идут буквы c, и их должно быть столько же.

Ответь себе до чтения: можно ли придумать такой порядок действий со стеком, чтобы проверить все три количества? Нельзя, и дело не в недостатке изобретательности. Сверяя b с a, автомат вынужден снимать то, что положил: иначе до счёта ему не добраться. К началу букв c стек пуст, и сравнивать их не с чем. Можно класть по два символа на каждую a, можно считать b поверх a - всякий раз что-то одно оказывается закопано под другим.

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

Застёжка-молния. Она соединяет два ряда зубцов, и соединяет идеально: зубец к зубцу, сколько бы их ни было. Третий ряд в ту же молнию не вставить.

Правило грамматики S → aSb и есть такая молния: одно применение добавляет букву слева и букву справа. Растут всегда два места строки одновременно. Чтобы уравнять три группы букв, идущие одна за другой, одной молнии мало, а две молнии, застёгнутые на одной строке, друг о друге ничего не знают.

Механизм: повтор на пути дерева

Возьмём грамматику в нормальной форме Хомского с k нетерминалами. Дерево разбора в ней двоичное: у каждого внутреннего узла два ребёнка, кроме узлов над самыми листьями. Двоичное дерево высоты h имеет не больше 2ʰ листьев. Значит, у строки длиннее 2ᵏ дерево выше k, и на самом длинном пути от корня к листу нетерминалов больше, чем их есть в грамматике. Какой-то нетерминал A встречается на этом пути дважды.

                 S
               / | \
              u  A  z            верхнее A порождает кусок  v x y
                / | \
               v  A  y           нижнее A порождает кусок  x
                  |
                  x

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

Строка разрезана на пять частей u v x y z. Из верхнего A выводится v x y, из нижнего - x. Оба узла - один и тот же нетерминал, поэтому поддеревья взаимозаменяемы:

нижнее поддерево на место верхнего:   u x z              v и y исчезли
верхнее на место нижнего:             u v v x y y z      v и y удвоились
повторить ещё раз:                    u v v v x y y y z

Все эти строки выводятся по той же грамматике. Это лемма о накачке для КС-языков: у любого КС-языка есть число p такое, что любую его строку длины не меньше p можно разрезать на u v x y z, где хотя бы один из кусков v и y непуст, кусок v x y не длиннее p, и все строки u vⁱ x yⁱ z при i = 0, 1, 2, … лежат в языке. Непуст хотя бы один кусок потому, что у верхнего A два ребёнка: нижнее A лежит под одним из них, а второй даёт непустую часть строки. Ограничение на длину v x y получается так. Повтор ищут в нижней части самого длинного пути: среди последних k + 1 нетерминалов на нём какой-то обязан повториться. Путь самый длинный во всём дереве, значит и в поддереве верхнего A длиннее нет: высота этого поддерева не больше k + 1, листьев в нём не больше 2ᵏ⁺¹. Это число и берут в качестве p: строка такой длины заведомо длиннее 2ᵏ, и повтор в ней есть.

У регулярных языков накачивался один кусок. Здесь два, и накачиваются они синхронно - та самая молния.

Почему aⁿbⁿcⁿ не КС-язык. Пусть он КС-язык и p - число из леммы. Возьмём строку aᵖbᵖcᵖ. Кусок v x y не длиннее p, а между последней a и первой c лежит p букв b: значит, в кусок не могут попасть одновременно буквы a и буквы c. Накачка меняет количество букв хотя бы одного вида (один из кусков непуст) и не более чем двух из трёх - третье остаётся прежним, и равенство нарушено. Если же v или y захватывает буквы двух видов, после удвоения нарушается порядок. В любом случае накачанная строка не в языке. Противоречие.

Правило

У любого КС-языка длинные строки накачиваются в двух местах сразу: u vⁱ x yⁱ z, причём v x y короткий. Язык, в котором это невозможно, не контекстно-свободен: так доказывается для aⁿbⁿcⁿ и для языка «слово, повторённое дважды» над алфавитом хотя бы из двух букв (там накачивают строку aᵖbᵖaᵖbᵖ; над одной буквой это просто строки чётной длины). КС-языки замкнуты относительно объединения, сцепления и повтора, но не замкнуты относительно пересечения и дополнения. Пересечение КС-языка с регулярным - снова КС-язык.

Разбор: все разрезы до одного

Довод выше говорит «для любого разреза». Проверим его перебором: для строки a⁴b⁴c⁴ и p = 4 функция nakachka перебирает все разрезы с куском v x y не длиннее p и непустыми в сумме v и y и считает, при скольких из них и строка без v и y, и строка с удвоенными v и y остаются в языке. Третий параметр, v_yazyke, - функция, которая проверяет, лежит ли строка в языке. Кусок v x y задан началом и длиной; v - его первые dv символов, y - последние dy, x - то, что между ними. Для сравнения - то же для строки a⁴b⁴ и языка aⁿbⁿ.

def tri_porovnu(s):
    n = len(s) // 3
    return len(s) % 3 == 0 and s == "a" * n + "b" * n + "c" * n

def dva_porovnu(s):
    n = len(s) // 2
    return len(s) % 2 == 0 and s == "a" * n + "b" * n

def nakachka(stroka, p, v_yazyke):
    razbienij = 0
    vyzhilo = 0
    primer = ""
    for nachalo in range(len(stroka)):
        for dlina in range(1, p + 1):
            if nachalo + dlina > len(stroka):
                break
            for dv in range(dlina + 1):
                for dy in range(dlina - dv + 1):
                    if dv + dy == 0:
                        continue
                    u = stroka[:nachalo]
                    v = stroka[nachalo:nachalo + dv]
                    x = stroka[nachalo + dv:nachalo + dlina - dy]
                    y = stroka[nachalo + dlina - dy:nachalo + dlina]
                    z = stroka[nachalo + dlina:]
                    razbienij = razbienij + 1
                    if (v_yazyke(u + x + z)
                        and v_yazyke(u + v + v + x + y + y + z)):
                        vyzhilo = vyzhilo + 1
                        primer = v + "|" + x + "|" + y
    return [razbienij, vyzhilo, primer]

p = 4
print(nakachka("a" * p + "b" * p + "c" * p, p, tri_porovnu))
print(nakachka("a" * p + "b" * p, p, dva_porovnu))

[295, 0, '']
[175, 7, 'a|bb|b']

Для трёх количеств перебрано 295 разрезов, и ни один не пережил накачку. Для двух - 175 разрезов, семь годятся; последний найденный - v = a, x = bb, y = b: удвоение даёт a⁵b⁵, удаление - a³b³. Все семь устроены одинаково: v состоит из букв a, y - из стольких же букв b.

Перебор при p = 4 не доказательство: в лемме p не известно и может быть любым. Доказательство - довод из механизма, который годится для каждого p. Программа показывает, что именно этот довод утверждает: не «мы не нашли разрез», а «разреза нет».

Разбор: два КС-языка, пересечение которых не КС-язык

Язык «сколько-то букв a, столько же букв b, потом сколько угодно c» контекстно-свободен: S → X C, X → aXb | ε, C → cC | ε. Язык «сколько угодно a, потом сколько-то b и столько же c» - тоже: S → A Y, A → aA | ε, Y → bYc | ε. Функция porodit из первого урока главы строит оба языка до длины 6.

def porodit(pravila, start, dlina):
    gotovye = []
    ochered = [start]
    videli = {start}
    i = 0
    while i < len(ochered):
        forma = ochered[i]
        i = i + 1
        mesto = -1
        for j in range(len(forma)):
            if forma[j] in pravila:
                mesto = j
                break
        if mesto == -1:
            gotovye.append(forma)
            continue
        for pravaya in pravila[forma[mesto]]:
            novaya = forma[:mesto] + pravaya + forma[mesto + 1:]
            bukv = 0
            for simvol in novaya:
                if simvol not in pravila:
                    bukv = bukv + 1
            if bukv <= dlina and novaya not in videli:
                videli.add(novaya)
                ochered.append(novaya)
    return gotovye

pervyj = porodit({"S": ["XC"], "X": ["aXb", ""], "C": ["cC", ""]},
                 "S", 6)
vtoroj = porodit({"S": ["AY"], "A": ["aA", ""], "Y": ["bYc", ""]},
                 "S", 6)
print(len(pervyj), len(vtoroj))
print(sorted(pervyj)[:8])
obshchie = []
for s in pervyj:
    if s in vtoroj:
        obshchie.append(s)
print(obshchie)

16 16
['', 'aaabbb', 'aabb', 'aabbc', 'aabbcc', 'ab', 'abc', 'abcc']
['', 'abc', 'aabbcc']

В каждом языке по шестнадцать строк не длиннее шести символов, общих три: пустая, abc и aabbcc. Пересечение - строки, где одновременно a и b поровну и b и c поровну, то есть aⁿbⁿcⁿ. Каждое условие по отдельности проверяет одна молния; оба сразу - уже нет.

Отсюда таблица замкнутости:

операция                         регулярные       контекстно-свободные
объединение, сцепление, повтор      да                  да
пересечение                         да                  нет
дополнение                          да                  нет
пересечение с регулярным языком     да                  да

Три «да» дают правила для нового начального нетерминала: S → S₁ | S₂ для объединения, S → S₁ S₂ для сцепления, S → S₁ S | ε для повтора. Дополнение отпадает вслед за пересечением: пересечение двух языков - это дополнение объединения их дополнений, и если бы дополнение КС-языка всегда было КС-языком, таким было бы и пересечение. С регулярным языком КС-язык пересекать можно: магазинный и конечный автоматы запускаются одновременно, и состоянием служит пара их состояний, а стек по-прежнему один.

Обе модели - ступени одной лестницы, иерархии Хомского:

вид правил грамматики         модель                        пример языка
A → aB,  A → a,  A → ε        конечный автомат              a*b*
A → любая строка              магазинный автомат            aⁿbⁿ, скобки
правая часть не короче левой  машина с памятью длины входа  aⁿbⁿcⁿ, n ≥ 1
любые                         машина Тьюринга               всё, что
                                                            распознаётся

В первой строке нетерминал - состояние автомата, а правило A → aB - переход по букве a. В третьей слева в правиле разрешено несколько символов, например AB → BA; строку они не укорачивают, поэтому пустую вывести нельзя и пример взят при n ≥ 1. «Память длины входа» - это машина Тьюринга, которой запрещено выходить за клетки, занятые входом. Каждая ступень строго шире предыдущей. На верхней стоит машина ТьюрингаРазбирается в разделе 21, глава «Машина Тьюринга и что считается вычислением»: Машина Тьюринга: лента, головка и таблица - модель из следующей главы.

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

От грамматики требуют того, что она не выражает. «Переменная объявлена до использования» - это язык вида «слово встречается дважды», и он не контекстно-свободен. Компилятор проверяет это не разборщиком, а следующим проходом по дереву.

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

Два разборщика «соединены условием И». Каждое условие контекстно-свободно, а оба вместе - не обязательно. Написать одну грамматику для пересечения может быть невозможно.

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

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

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

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

Выбор модели под задачу. Лестница отвечает на вопрос «какой инструмент минимально достаточен»: формат без вложенности - автомат; вложенность - стек; согласование трёх мест или сравнение копий - полноценная программа.

Теперь сам

1. Контекстно-свободен ли язык aⁿbᵐcⁿ - букв a и c поровну, букв b сколько угодно?
2. А язык aⁿbᵐcⁿdᵐ?
3. Сколько листьев может быть у двоичного дерева высоты 5 и что из этого следует для грамматики с пятью нетерминалами?
4. Язык L контекстно-свободен, язык R регулярен. Что можно сказать о L ∩ R?
5. Почему из того, что строки языка накачиваются, не следует, что он контекстно-свободен?