Лекция 11. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ

Содержание лекции

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

Пусть X -- конечный алфавит (т.е. конечное множество символов). Детерминированным конечным автоматом (ДКА) называется ориентированный граф, у которого ребра помечены элементами алфавита X, причем

• ровно одна вершина графа отмечена как начальная;
• некоторые вершины отмечены как конечные, множество конечных вершин непусто (вершина может быть одновременно и начальной, и конечной);
• 3) не может существовать двух ребер, выходящих из одной и той же вершины и помеченных одной и той же буквой.

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

Вершины графа конечного автомата иногда называют состояниями, ребра -- переходами.

Можно несколько ослабить требования к графу конечного автомата. А именно,

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

Язык, задаваемый недетерминированным КА, определяется точно так же, как и в случае детерминированного КА.

Примеры

1. Детермимнированный КА

2. Недетерминированный КА

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

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

Предложение. Для всякого недетерминированного конечного автомата можно построить детерминированный конечный автомат, задающий точно такой же язык. Вершины ДКА -- это подмножества множества вершин исходного НКА. Чтобы получить вершину ДКА (т.е. множество вершин исходного НКА), в которую осуществляется переход по данному символу из данной вершины ДКА (т.е. из множества M вершин НКА), надо объединить все вершины НКА, которые получаются всевозможными переходами по данному символу из всех вершин множества M, а затем добавить также вершины, достижимые с помощью переходов по пустой цепочке. Начальная вершина ДКА -- это объединение всех начальных вершин НКА плюс вершины, достижимые из начальных с помощью переходов по пустым цепочкам. Конечные вершины ДКА -- это подмножества вершин исходного НКА, содержащие хотя бы одну конечную вершину.

Проиллюстрируем алгоритм построения ДКА для заданного НКА на примере. Рассмотрим НКА из примера 2. Будем последовательно строить переходы. Из состояния 1 по символу b попадаем в состояние 1, по символу a попадаем в состояние 1+2.

Число вершин ДКА, вообще говоря, экспоненциально зависит от числа вершин исходного НКА.

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

Лемма о разрастании для автоматных языков. Пусть L -- язык, заданный конечным автоматом. Тогда существуют натуральные числа K и N такие, что если цепочка u длины не меньше N принадлежит L, то ее можно представить в виде

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

Задача. Докажите, что язык, состоящий из цепочек вида

Регулярные выражения

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

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

1. Пустой язык (т.е. язык, не содержащий ни одной цепочки) является регулярным.
2. Язык, состоящий из пустой цепочки, является регулярным. Регулярное выражение: пустое, или ().
3. Язык, состоящий из одной однобуквенной цепочки, является регулярным. Регулярное выражение: a, или (a) (для цепочки, состоящей из буквы "a").
4. Объединение двух регулярных языков регулярно. Пусть язык L1 задается выражением e1, язык L2 -- выражением e2. Тогда объединение задается выражением e1 | e2, или (e1 | e2).
5. Конкатенация двух регулярных языков регулярна. Пусть язык L1 задается выражением e1, язык L2 -- выражением e2. Конкатенация L1 и L2 состоит из цепочек вида vw, где v принадлежит L1, w принадлежит L2. Регулярное выражение: e1 e2, или (e1 e2).
6. Итерация регулярного языка регулярна. Пусть язык L задается выражением e. Итерация L* состоит из всех конечных цепочек вида u1 u2 ... un,     n >= 0, где ui принадлежат языку L, включая пустую цепочку. Регулярное выражение: e*, или (e)*.

Пример. Рассмотрим язык из примера 1, заданный конечным автоматом

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

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

1. Для пустой цепочки используем автомат с двумя вершинами, соединенными стрелкой, не помеченной никакой буквой (или помеченной пустой цепочкой). 1 --> 2 В случае однобуквенной цепочки стрелка помечена этой буквой.
2. В случае конкатенации языков L1 и L2 (L = L1 L2) построим автомат +-------------+ +-------------+ 1 --> | A ->...-> B | --> | C ->...-> D | --> 2 +-------------+ +-------------+ где автомат с начальной вершиной A и конечной вершиной B задает язык L1, автомат с начальной вершиной C и конечной вершиной D задает язык L2. Начальная вершина построенного автомата -- вершина 1, конечная -- вершина 2, дополнительные стрелки помечены пустой цепочкой.
3. В случае объединения языков L1 и L2 (L = L1|L2) построим автомат +-------------+ +--> | A ->...-> B | --> / +-------------+ \ 1 2 \ +-------------+ / +--> | C ->...-> D | --> +-------------+
4. Наконец, в случае итерации L* используем автомат +---------------+ 1 --> | A ->...-> B | --> 2 +- | ------ | -+ | | +--- <----+ (мы "зациклили" автомат исходного языка L, добавив ребро, ведущее из конечной вершины B в начальную вершину A).

Нетривиальная часть доказательства состоит в доказательстве прямой импликации: автоматный язык является регулярным. Рассмотрим детерминированный конечный автомат, задающий язык L, с начальной вершиной 1 и некоторым непустым множеством конечных вершин. Пусть вершины автомата занумерованы числами 1, 2,..., n. Обозначим через L(i,j,k) язык, состоящий из цепочек, соответствующих всем путям в графе конечного автомата, удовлетворяющим следующим условиям:

• путь начинаются в вершине i и заканчиваются в вершине j;
• все промежуточные вершины пути принадлежат множеству {1,2,...,k} (отметим, что начальная и конечная вершины пути, т.е. i и j, могут не принадлежать этому множеству).

Доказательство будем вести индукцией по k. При k = 0 язык L(i,j,0) состоит из конечного числа одноэлементных цепочек, соответствующих всем ребрам, ведущим из вершины i в вершину j. Если таких нет, то L(i,j,0) -- пустой язык.

Пусть доказано, что для фиксированного k и для любой пары (i,j) язык L(i,j,k) регулярен. Докажем, что язык L(i,j,k+1) регулярен. Рассмотрим путь из вершины i в вершину j, у которого все промежуточные вершины принадлежат множеству {1,2,...,k,k+1}. Всякий такой путь либо вообще не заходит в вершину k+1 и, следовательно, принадлежит множеству L(i,j,k), либо несколько раз заходит в вершину k+1. В последнем случае он разбивается на следующие участки:

• участок от начальной вершины до первого вхождения в вершину k+1; такие пути соответствуют регулярному выражению L(i,k+1,k);
• несколько раз могут повторяются участки с началом и концом в вершине k+1 и промежуточными вершинами из множества {1,2,...,k}; соответствующее регулярное выражение L(k+1,k+1,k)*;
• конечный участок от вершины k+1 до вершины j, регулярное выражение L(k+1,j,k).