Леммы о разрастании для регулярных и контекстно-свободных языков05.05.2020 12:22

Две леммы о разрастании — утверждения, использующиеся для доказательства ограниченности важных классов формальных языков: регулярных и контекстно-свободных. Важность этих классов для программистов понять легко: регулярные выражения (один из видов описания регулярных языков) в работе используются достаточно часто, а уж языки программирования, синтаксис которых описывается контекстно-свободными грамматиками, и подавно.

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

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

ht7olsx0ioszanmxcj4gamznyti.png

КДПВ иллюстрирует процесс разрастания для КС-грамматик

Формальный язык — произвольное множество строк (то есть, просто последовательностей) в конечном алфавите символов. Алфавит обычно обозначают большой сигмой: $\Sigma$. Специальным образом выделяется пустое слово, т.е. слово нулевой длины, не содержащее ни одного символа: $\varepsilon$.

Если язык конечный (т.е. содержит некоторое конкретное число различных слов), описать его просто: можно предъявить все входящие в него слова. Поэтому интересно обсуждать описания потецинально бесконечных языков. Таких способов придумано очень много, но сегодня мы обсудим два вполне конкретных.


1. Регулярные языки и регулярные выражения

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

Простейшие языки, относящиеся к классу регулярных:


  • $\varnothing$ — язык, не содержащий ни одного слова;
  • $\{\varepsilon\}$ — язык, содержащий только одно, пустое, слово;
  • $\{a\}, a \in \Sigma$ — язык, содержащий одно однобуквенное слово.

Теперь можно ввести операции над регулярными языками. Если $A$ и $B$ — регулярные языки, регулярными языками также будут следующие:

Замечание: я использую обозначение $ \mathbb{N}_0 = \mathbb{N} \cup \{0\}$, чтобы избежать полемики по вопросу о том, является ли ноль натуральным числом

Для простоты записи знак конкатенации часто опускают: $A \cdot B = AB$.

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

http[s]?://(?:[a-zA-Z]|[0-9]|[$-_@.&+]|[!*\(\),]|(?:%[0-9a-fA-F][0-9a-fA-F]))+

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

В языках программирования вы можете встретить дополнительные операции: диапазоны ([0-9]), опциональные символы ([s]?), непустые итерации (a+ — то же, что aa*, т.е. элемент повторяется не менее одного раза) и другие. Они служат лишь для получения более компактных записей, никак не влияя на то, какие в принципе языки можно описывать при помощи регулярных выражений.

Если же обходиться без дополнительных операций, регулярные выражения обычно записываются при помощи символов (в том числе цифр), знаков | (объединение), * (итерация) и скобок. Конкатенация специальным образом не выделяется, она выражается следованием символов друг за другом.

Например, запишем такое регулярное выражение:

$abc(de^*f|de)$

Оно описывает язык, состоящий из следующих строк: 

abcde
abcdf
abcdef
abcdeef
abcdeeef
abcdeeeef

и так далее.


2. Конечные автоматы

Конечные автоматы являются ещё одним способом представления регулярных языков. Конечный автомат — это ориентированный конечный граф, дуги которого взвешены символами алфавита. Одна из вершин графа считается начальной, при этом несколько вершин могут считаться конечными (терминальными). Вершины этого графа называются состояниями автомата.

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

Если в определённый момент из состояния нет исходящей дуги, соответствующей текущему символу входной строки, автомат отклоняет строку. Если строка завершилась, а автомат не достиг терминального состояния, строка также отклоняется. Наконец, если по завершению входной строки автомат оказался в терминальном состоянии — строка считается принятой и принадлежащей языку, который описывается этим автоматом.

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

u2mikxbnmlo0quw5vc1hi7xvrsm.png
Пример конечного автомата, эквивалентного регулярному выражению bab|aab+a

Теперь будем по одной удалять состояния конечного автомата. Пусть $a_i$, $a_j$, $a_k$ — вершины автомата. Из $a_i$ можно попасть в $a_k$ непосредственно, соответствующая дуга взвешена языком $L_{ik}$. Аналогично, дуга из $a_i$ в $a_j$ взвешенна языком $L_{ij}$, а из $a_j$ в $a_k$ — $L_{jk}$. Нельзя забывать, что вершина $a_j$ может иметь петлю, взвешенную языком $L_{jj}$.

Удалим вершину $a_j$, а вершины $a_i$ и $a_k$ свяжем дугой, взвешенной языком

$L^{'}_{ik} = L_{ik} \cup L_{ij} \cdot L^{*}_{jj} \cdot L_{jk}$

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

a4w8bm2fqkmtsx5dzw68109v6ig.png
Удаление вершины с петлёй в конечном автомате из предыдущего примера

Удаляя так вершину за вершиной из исходного автомата, мы получим автомат, содержащий только начальную и несколько конечных вершин. Это не очень удобно, поэтому свяжем все терминальные вершины автомата с какой-нибудь одной из них дугами, взвешенными регулярным выражением $\varepsilon$. Эта избранная терминальная вершина останется единственной терминальной вершиной модифицированного автомата, и тогда результатом удаления всех возможных вершин будет автомат с одной начальной вериной и одной конечной вершиной. Они будут связаны дугой, вес которой и будет искомым регулярным выражением.

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

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

dyx-wv9tynnafoyxcbry-2fp3yw.png

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


3. Лемма о разрастании для регулярных языков

Рассмотрим язык $L = \{a^nb^n | n \in \mathbb{N}_0 \}$. Он содержит строки $\varepsilon$, $ab$, $aabb$, $aaabbb$ и так далее. Является ли он регулярным? Представим себе, что да.

В таком случае соответствующий конечный автомат, очевидно, содержит хотя бы один цикл. В действительности понадобится, по всей видимости, два цикла: один для того, чтобы генерировать сколь угодно длинные последовательности из букв $a$ и другой — для последовательностей из букв $b$. Как гарантировать, что циклы будут совершать равное число итераций? Ведь у конечного автомата нет памяти… Может быть, соответствующего конечного автомата не существует, а язык не является регулярным?

И действительно, не является! Интуитивное соображение, приведённое выше, можно перестроить строго математически. Результатом этого будет


Лемма о разрастании регулярных языков. Для любого регулярного языка $L$ существует число $n \in \mathbb{N}$ такое, что $\forall w \in L, |w| \ge n$ найдутся такие три слова $x$, $y$, $z$, что: $w = xyz$; $y \ne \varepsilon$; $|xy| \le n $; $\forall k \ge 0: xy^kz \in L$.


Доказательство леммы

Пусть $L$ — регулярный язык, которому соответствует конечный автомат с числом вершин $n$, а $w \in L$ — слово длины не менее $n$.

Рассмотрим последовательность вершин конечного автомата в порядке их посещения при разборе слова $w$: $a_0$, $a_1$, $a_2$, …, $a_m$. Последовательность, очевидно, содержит $m+1$ вершину, и $m \ge n$.

Так как всего в графе только $n$ вершин, хотя бы одна из них повторяется в последовательности. Пусть $a_i$ — первая вершина последовательности из числа повторяющихся, причём второй раз она встретилась в позиции $j$. Тогда $x$ — первые $i$ символов строки $w$, $y$ — отрезок $w$, соответствующий перемещению из $a_i$ в $a_j$, а $z$ — отрезок $w$, соответствующий перемещению из $a_j$ в $a_n$.

Так как переход от $a_i$ к $a_j$ образует цикл в конечном автомате, по этому циклу можно пройти произвольное (в том числе и нулевое!) число раз, и всякий раз будет получаться строчка, принимаемая автоматом, поэтому $\forall k \in \mathbb{N}_0: xy^kz \in L$.

При этом пара состояний $a_i$, $a_j$ — первый повтор в рассматриваемой последовательности. Значит, все состояния $a_0$, $a_1$, …, $a_{j-1}$ являются различными. Раз так, то их не больше $n$. Отсюда получаем, что $j \le n$ и $|xy| \le n$, что и требовалось.

Другими словами: в любом достаточно длинном слове найдётся непустая, но не совпадающая со всем словом часть, которую можно повторять произвольное (в т.ч. нулевое) число раз, оставаясь при этом в рамках того же регулярного языка, что и исходное слово.

Попробуем применить эту лемму к языку $L = \{a^nb^n | n \in \mathbb{N}_0\}$. Пусть $n$ — то самое число из леммы для соответствующего регулярного языка. Тогда строку $a^nb^n$ можно представить в виде $a^nb^n = xyz$,
причём $|xy|\le n$, а, значит, строка $xy$ содержит только символы $a$. Строка $y$ поэтому тоже содержит только символы $a$, да ещё и является непустой согласно утверждению леммы. Тогда строки вида $xy^kz$ для $k>1$» /> будут содержать строго больше символов <img src=, чем символов $b$ и, стало быть, не принадлежат языку $L$. Но их принадлежность языку следует из леммы и условия регулярности $L$. Следовательно, $L$ не является регулярным языком!

Аналогично можно доказать нерегулярность языка $(^n)^n$, который является подмножеством множества всех правильных скобочных последовательностей. А вслед за ним нерегулярным оказывается и весь язык правильных скобочных последовательностей.


4. Контекстно-свободные грамматики

Грамматики — способ определения языков, основанный на операции постановки строки вместо подстроки.

Алфавит в грамматиках разбит на две части: терминальные символы (терминалы) $T$ и нетерминальные символы (нетерминалы) $N$; $\Sigma = N \cup T$. Среди нетерминалов выделен специальный символ $S \in N$ — аксиома грамматики.

Ключевой частью грамматики являются правила вывода $P$. Правила вывода можно описать как бинарное отношение $\varphi$ на множестве строк в алфавите $\Sigma$: если $(s_1, s_2) \in \varphi$, то правилами грамматики разрешено заменять любое вхождение строки $s_1$ на строку $s_2$. Это бинарное отношение можно воспринимать как многозначную функцию: для каждой левой части может быть определено несколько различных правых частей. Обычно, если $(s_1, s_2) \in \varphi$, пишут просто $s_1 \rightarrow s_2$.

Строка $\beta$выводится за один шаг из строки $\alpha$, если эти строки допускают представление в виде $\alpha = xs_1z$, $\beta = xs_2z$ и при этом $(s_1, s_2) \in \varphi$. То есть, вывод за один шаг — это замена подстроки в соответствии с правилами вывода. Будем это отношение обозначать так: $\alpha \vdash \beta$.

Скажем, что строка $\beta$выводится из строки $\alpha$ (за произвольное число шагов), если существует последовательнось строк $s_0 = \alpha $, $s_1$, $s_2$, …, $s_{k+1}=\beta$, в которой каджая строка выводится за один шаг из предыдущей: $s_i \vdash s_{i+1}$. В таком случае будем писать $\alpha \Rightarrow \beta$.

Строка $s$допускается грамматикой, если она состоит только из терминальных символов и при этом выводится из аксиомы: $s \in T^*$, $S \Rightarrow s$. Язык, определяемый грамматикой, состоит из всех допускаемых ею строк.

Осталось добавить, что грамматика называется контекстно-свободной (КС-грамматикой), если все левые части правил вывода — единичные нетерминалы. Языки, описываемые контекстно-свободными грамматиками, называются контекстно-свободными языками.

Например, такая КС-грамматика описывает правильные скобочные последовательности:

$S \rightarrow (S)S$
$S \rightarrow \varepsilon$

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

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

def BuildPath(queue, parents, parent):
    path = []
    while parents[parent] != parent:
        path += [queue[parent]]
        parent = parents[parent]
    return path[::-1]

def Solve(rules, target):
    queue = ['S']
    parents = [0]

    idx = 0
    while idx < len(queue):
        current = queue[idx]

        for rule in rules:
            entryIdx = current.find(rule[0])
            while entryIdx != -1:
                new = current[:entryIdx] + rule[1] + current[entryIdx + len(rule[0]):]

                if new == target:
                    path = [queue[0]] + BuildPath(queue, parents, idx) + [new]
                    return path

                queue.append(new)
                parents.append(idx)

                entryIdx = current.find(rule[0], entryIdx + 1)

        idx += 1

Такая реализация работает, конечно, очень медленно и, кроме того, вообще не завершает работу, если строка не выводится грамматикой; однако эта реализация вполне подходит для демонстрационных целей! Вот и в данном случае: 

rules = [
    ("S", "(S)S"),
    ("S", ""),
]
target = "(()())()"
print('\n'.join(Solve(rules, target)))

S
(S)S
((S)S)S
((S)(S)S)S
((S)(S)S)(S)S
(()(S)S)(S)S
(()()S)(S)S
(()())(S)S
(()())()S
(()())()

Можно построить КС-грамматику и для языка $L = \{a^nb^n | n \in \mathbb{N}_0\}$: 

rules = [
    ("S", "aSb"),
    ("S", ""),
]
target = "aaabbb"
print('\n'.join(Solve(rules, target)))

S
aSb
aaSbb
aaaSbbb
aaabbb

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

Тем не менее, и КС-грамматики описывают не всё.


5. Лемма о разрастании для КС-грамматик

Рассмотрим язык $L = \{ a^nb^nc^n | n \in \mathbb{N}_0 \} $. Мы уже знаем, что контекстно-свободные грамматики позволяют строить строки вида $a^nb^n$, так что, видимо, надо будет сделать как-то так:

$S \rightarrow \varepsilon$
$S \rightarrow AB$
$A \rightarrow aAb$
$B \rightarrow Bc$
$A \rightarrow \varepsilon$
$B \rightarrow \varepsilon$

Такая грамматика построит язык $a^nb^nc^m$. Как же добиться, чтобы $m$ всегда совпадало с $n$? Ведь подстановки действуют локально и ничего «не знают» ни о строке в целом, ни о том, сколько раз были применены другие подстановки. И, действительно, добиться этого невозможно. Данный язык не является контекстно-свободным, и установить это позволяет


Лемма о разрастании контекстно-свободных грамматик. Для любого контекстно-свободного языка $L$ существует число $n \in \mathbb{N}$ такое, что $\forall w \in L, |w| \ge n$ найдутся такие слова $u$, $v$, $x$, $y$, $z$, что: $w = uvxyz$; $vy \ne \varepsilon$; $|vxy| \le n $; $\forall k \ge 0: uv^kxy^kz \in L$.


Доказательство леммы

Для доказательства нам потребуется вначале привести грамматику к нормальной форме Хомского, воспользовавшись соответствующим алгоритмом.

В этой форме в правых частях правил вывода могут находиться либо два нетерминала, либо один терминал. Пустая строка может находиться в правой части, только если в левой находится аксиома. Итак, разрешены правила следующих трёх видов:
$S \rightarrow \varepsilon$
$A \rightarrow BC$
$A \rightarrow a$

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

sivzitaqlm1s9bx4mx6k78xck1o.png
Пример КС-грамматики и дерева разбора для строки acd

Итак, пусть грамматика находится в нормальной форме. Выберем $n=2^{|N|+1}$, где $|N|$ — общее число нетерминалов в грамматике, и пусть $w \in L, |w| \ge n$. Тогда для этого слова можно построить дерево разбора. Дерево разбора — бинарное, т.к. грамматика находится в нормальной форме. Значит, высота дерева $m$ не может быть меньше, чем $|N|+1$. Эта высота является числом нетерминалов, которые встречаются на пути из корня дерева до одного из листов-терминалов. Раз число нетерминалов в этом пути превосходит число различных нетерминалов в грамматике, как минимум один из них повторяется.

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

Нетерминал $B$ встречается в дереве разбора, поэтому существует вывод $S \vdash uBz$. $B$ также встречается в поддереве, в корне которого записан сам нетерминал $B$, поэтому существует вывод $B \rightarrow vBy$, причём $vy \ne \varepsilon$, т.к. в нормальной форме нетерминал порождает как минимум два нетерминала, каждый из которых затем превращается как минимум в один терминал. Последнее вхождение $B$ порождает некоторую строку $x$.

9vxz0pqbziyamw5xcvhggch1oae.png

Итого:

Значит, $\forall k \in \mathbb{N}_0 S \vdash uv^kxy^kz$, причём $vy \ne \varepsilon$.

Осталось лишь получить ограничение на длину строки $vxy$. Т.к. эта строка выводится из поддерева нетерминала $B$, а в этом дереве нет повторяющихся нетерминалов, высота дерева ограничена общим числом нетерминалов $|N|$. Значит, полученная строка не может иметь длину больше чем $2^{|N|+1} = n$. Так что $|vxy| \le n$.

Применим эту лемму к языку $ L = \{ a^nb^nc^n | n \in \mathbb{N}_0\} $. Предположим, что он является контекстно-свободным. Тогда выполнена лемма о разрастании, и пусть $n$ — то самое число из леммы. Рассмотрим слово $a^nb^nc^n$.

Для него выполнено утверждение леммы, так что $a^nb^nc^n=uvxyz$, причём $|vxy| \le n$ и $vy \ne \varepsilon$. Значит, строка $vxy$ не является пустой и при этом не содержит либо символ $a$, либо символ $c$, ведь эти символы разделяются последовательностью из $n$ символов $b$.

Тогда все строки вида $uv^kzy^kz$ также принадлежат рассматриваемому языку. Для $k>1$» /> они будут содержать различное число символов <img src= и $c$, и, следовательно, не будут относиться к языку $L$. Следовательно, он не является контекстно-свободным!



6. Грамматики общего вида

Что же, теперь терпеливый читатель умеет доказывать ограниченность регулярных и контекстно-свободных языков. В качестве завершения продемонстрирую, как построить язык $ L = \{ a^nb^nc^n | n \in \mathbb{N}_0 \}$, используя грамматику общего вида.

Начнём с правил для аксиомы грамматики:

$S \rightarrow \varepsilon$
$S \rightarrow aHbCE$

Нетерминал $E$ будет указывать, где находится граница между группами из символов $b$ и $c$. Поэтому в конечном счёте его достаточно превращать в пустую строку:

$E \rightarrow \varepsilon$

Нетерминал $H$ обеспечивает строительство строк неограниченной длины:

$H \rightarrow aHbC$
$H \rightarrow \varepsilon$

Наконец, нужно обеспечить, чтобы нетерминалы $C$ перемещались в правый участок строки и там превращались в терминалы $c$. Тут-то и пригодятся правила со сложными левыми частями!

$Cb \rightarrow bC$
$CE \rightarrow Ec$

Вот и всё! Применяя программу из пункта 5 к этим правилам вывода, получим: 

rules = [
    ("S", "aHbCE"),
    ("H", ""),
    ("H", "aHbC"),
    ("Cb", "bC"),
    ("CE", "Ec"),
    ("E", ""),
]
target = "aaabbbccc"
print('\n'.join(Solve(rules, target)))

S
aHbCE
aaHbCbCE
aaaHbCbCbCE
aaaHbbCCbCE
aaaHbbCbCCE
aaaHbbbCCCE
aaaHbbbCCEc
aaaHbbbCEcc
aaaHbbbEccc
aaaHbbbccc
aaabbbccc

У получившегося алгоритма есть интересная особенность: правила со сложной левой частью позволяют как бы «перемещать» группы символов; в данном случае нетерминалы $C$ перемещаются в правую часть строки. Похожий паттерн часто встречается в алгоритмах для машин Тьюринга.

Он же используется при доказательстве эквивалентности (в некотором не самом простом смысле) машин Тьюринга и ассоциативных исчислений, основанных на грамматиках. Об этом расскажу как-нибудь в другой раз.

© Habrahabr.ru