Определение конечного автомата

А. А. Волосевич

Основы теории

конечных автоматов

Курс лекций

для студентов специальности I-31 03 04 Информатика

всех форм обучения

Минск 2012

Содержание

1. Определение конечного автомата

2. Эквивалентность конечных автоматов

3. Минимизация конечных автоматов

4. Конечные автоматы Мили и Мура

5. Автоматные языки

6. Лемма о накачке

7. Эквивалентность и минимизация автоматов-распознавателей

8. Недетерминированные конечные автоматы

9. Регулярные множества, выражения и языки

Литература

Определение конечного автомата

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

Даже если число различных входных сигналов конечно, число возможных входных историй бесконечно (счётно). Если автомат по-разному будет себя вести для каждой возможной предыстории, то такой «бесконечный» автомат должен иметь неограниченный ресурс – память, чтобы все эти предыстории как-то запоминать. Введём на множестве предысторий отношение эквивалентности. А именно, две предыстории будем считать эквивалентными, если они одинаковым образом влияют на дальнейшее поведение автомата. Очевидно, что для правильного функционирования достаточно, чтобы автомат запоминал класс эквивалентности, к которому принадлежит данная история.

Определение 1. (Внутренним) состоянием автомата называется класс эквивалентности его входных историй.

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

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

Рассмотрим пример конечного автомата. Опишем поведение родителя, отправившего сына в школу. Сын приносит двойки и пятёрки. Отец не хочет хвататься за ремень каждый раз, как только сын получит очередную двойку, и выбирает более тонкую тактику воспитания. Чтобы описать модель поведения отца, используем граф, в котором вершины соответствуют состояниям, а дуга, помеченная x/y, из состояния s в состояние q проводится тогда, когда автомат из состояния s под воздействием входного сигнала x переходит в состояние q с выходной реакцией y. Граф автомата, моделирующего поведение родителя, представлен на рис. 1.

Рис. 1. Автомат, описывающий поведение «умного» родителя.

Этот автомат имеет четыре состояния {s0, s1, s2, s3} и два входных сигнала – оценки, полученные сыном в школе: {2, 5}. Начиная с начального состояния s0 (оно помечено особо), автомат под воздействием входных сигналов переходит из одного состояния в другое и выдаёт выходные сигналы – реакции на входы. Выходы автомата будем интерпретировать как действия родителя так:

y0 – «брать ремень»;

y1 – «ругать»;

y2 – «успокаивать»;

y3 – «надеяться»;

y4 – «радоваться»;

y5 – «ликовать».

Определим конечный автомат формально.

Определение 2. Конечным автоматом (автоматом Мили) называется шестёрка объектов A=S, X, Y, s0, δ, λ, где:

S – конечное непустое множество (состояний);

X – конечное непустое множество входных сигналов (входной алфавит);

Y – конечное непустое множество выходных сигналов (выходной алфавит);

s0∈ S – начальное состояние;

δ: S× X⟶ S – функция переходов;

λ: S× X⟶ Y – функция выходов.

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

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

Вопросы и упражнения.

Реализуйте предлагаемые конечные автоматы. Представьте графическую реализацию, табличную и программную.

1. Лифт работает в двухэтажном доме и может выполнять команды: «открыть двери», «закрыть двери», «подняться на второй этаж», «спуститься на первый этаж». Изначально лифт находится на первом этаже, его двери открыты. Построить автомат, выполняющий программу для лифта. Выходные значение – новое состояние или признак некорректности программы.

2. Построить автомат для выдачи кофе. Кофе стоит 15 копеек, автомат принимает монеты по 5 и 10 копеек (выходные значения – «жду», «выдать кофе», «выдать кофе и сдачу», «возврат денег»).

3. Построить автомат, выбрасывающий лишние пробелы между словами предложения.

4. Построить конечный автомат, выдающий остаток от деления вводимого троичного числа на 4. Построить два варианта автомата: для случая, когда число вводится со старших разрядов, и для случая, когда число вводится с младших разрядов.

5. Показать, что не существует автономного конечного автомата, выдающего выходную цепочку вида: 101001000100001…10n1…