Конечные автоматы и регулярные выражения

Введение

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

1. Команда grep операционной системы Unix или похожие команды для поиска цепочек, встречающиеся в Web-браузерах или системах форматирования текста. В этих системах регулярные выражения применяются, чтобы описать шаблоны, которые пользователям необходимо найти в файле. Разные поисковые системы способны преобразовать регулярные выражения или в детерминированный конечный автомат (ДКА), или недетерминированный конечный автомат (НКА) и применить такой автомат к файлу, в котором реализуется поиск.
2. Генераторы лексических анализаторов. Лексические анализаторы выступают как компоненты компилятора, они способны разбить исходную программу на логические единицы (лексемы), которые состоят из одного или набора символов и обладают определенным смыслом. Генератор лексических анализаторов может получить формальные описания лексем, которые являются по сути регулярными выражениями, и формирует ДКА, распознающий, какая из лексем появилась на его входе.

Конечные автоматы и регулярные выражения

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

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

Приведём пример работы примитивного конечного автомата:

Рисунок 1. Пример работы примитивного конечного автомата. Автор24 — интернет-биржа студенческих работ

В состав этого конечного автомата входят следующие элементы:

1. Лента, представленная входной цепочкой.
2. Устройство считывания информации.
3. Блок управления, содержащий перечень правил переходов.

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

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

1. Вершины графа, должны соответствовать состояниям конечного автомата.
2. Направленные ребра графа, должны соответствовать функциям переходов (у всех ребер должен быть указан символ, по которому осуществляется переход).
3. Вершина, имеющая входящее в него ребро, которое не выходит ни из одного состояния, должно соответствовать исходному состоянию.
4. Конечные состояния конечного автомата следует помечать жирным контуром.

При помощи управляющей таблицы конечный автомат задаётся следующим образом:

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

Главным отличием ДКА и НКА является тот факт, что ДКА в процессе работы способен находится лишь в одном состоянии, а НКА в процессе работы может находиться в нескольких состояниях одновременно.

Примером работы НКА может служить идея американского физика Хью Эверетта, состоящая в том, что каждое событие способно разбить мир на несколько миров, в каждом из которых данное событие может закончиться по-разному. К примеру, в одном из миров Гитлер сумел выиграть Вторую мировую войну, в другом мире Ньютон вместо физики начал заниматься бизнесом и открытие законов классической механики случилось позже на пятьдесят лет. Для того чтобы сделать какие-либо выводы из функционирования автомата, необходимо реализовать изучение всех «миров».

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

Рассмотрим пример построения минимального ДКА по регулярному выражению. Основными операциями, применяемыми в регулярных выражениях, считаются следующие:

1. Операция итерации (замыкание Клини), которая обозначается при помощи символа «*».
2. Операция конкатенации, которая обозначается при помощи пробела или пустой строки (к примеру, ab).
3. Операция объединения, которая обозначается при помощи символа "|".

Имеется следующее регулярное выражение:

$xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)$

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

$(xy* | ab | (x | a*)) (x | y*)$

А далее можно построить автомат по данному регулярному выражению:

Рисунок 2. Автомат. Автор24 — интернет-биржа студенческих работ