Введение в теорию автоматов

Введение в теорию автоматов

2-е издание, исправленное

Князьков В.С.
Волченская Т.В.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Введение в теорию автоматов/ В.С. Князьков, Т.В. Волченская - М.: Национальный Открытый
Университет “ИНТУИТ”, 2016

Приводятся начальные сведения об абстрактных автоматах Мили и Мура. Даются возможные
способы представления автоматов: теоретико-множественное, графовое, табличное и матричное,
понятия реакции автомата и эквивалентных автоматов.
Приводятся методы взаимного эквивалентного преобразования автоматов. Приводятся общие
сведения о микропрограммном управлении, понятия микрокоманды, микрооперации,
микропрограммы, способы представления микропрограмм в виде граф-схем алгоритмов (ГСА) ,
формул переходов, матричных и логическим схем алгоритмов. Приводятся методы разметки ГСА и
правила построения по ним автоматов Мили и Мура. Дается понятие совмещенного автомата и
способы его представления. Рассматриваются методы канонического синтеза структурных
автоматов. Приводятся примеры синтеза памяти структурного автомата на базе RS-, Т– и Dтриггеров.

(c) ООО “ИНТУИТ.РУ”, 2008-2016
(c) Князьков В.С., Волченская Т.В., 2008-2016

3

Основные понятия теории абстрактных автоматов

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

Введение

“Теория автоматов” - является одной из важных компонент федерального
государственного стандарта по направлению “Информатика и вычислительная
техника”.

Теория автоматов имеет широкие возможности применения:

Проектирование систем логического управления;
Обработка текстов и построение компиляторов;
Спецификация и верификация систем взаимодействующих процессов;
Языки описания документов и объектно-ориентированных программ;
Оптимизация логических программ др.

Об этом можно судить по выступлениям на семинаре “Software 2000…” ученых и
специалистов.

Дуг Росс: “…80 или даже 90 % информатики (Computer Science) будет в будущем
основываться на теории конечных автоматов…”

Herver Gallaire: “Я знаю людей из “Боинга”, занимающихся системами стабилизации
самолетов с использованием чистой теории автоматов. Даже трудно себе представить,
что им удалось с помощью этой теории. “

Brian Randell : “Большая часть теории автоматов была успешно использована в
системных программах и текстовых фильтрах в ОС UNIX. Это позволяет множеству
людей работать на высоком уровне и разрабатывать очень эффективные программы”.

1.1. Основные понятия и определения.

Простейший преобразователь информации (рис.1.1,а) отображает некоторое множество
элементов информации Х, поступающее на вход, в некоторое множество на выходе Y.
Если множества Х и Y являются конечными и дискретными, то есть преобразование
осуществляется в дискретные моменты времени, то такие преобразователи
информации называются конечными преобразователями. Элементы множеств Х и Y в
этом случае предварительно кодируют двоичными кодами и строят преобразование
одного множества в другое.

Результат преобразования 
 зачастую зависит не только от того, какая

информация в данный момент появилась на входе, но и от того, что происходило
раньше, то есть от предыстории преобразования. Например, один и тот же вход 
4

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

Рис. 1.1. 

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

Рассмотрим несколько примеров.

Пример 11). Автомат, описывающий поведение “умного” отца.

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

выходные сигналы 
, которые будем интерпретировать как действия

родителя следующим образом:

 - брать ремень;

 - ругать сына;

 - успокаивать сына;

 - надеяться;

 - радоваться;

 - ликовать.

5

Рис. 1.2. 

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

успокаивать и т.д.

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

новому состоянию.

6

Рис. 1.3. 

Аппаратную реализацию автомата рассмотрим во второй части этого раздела.

Пример 2. “Студент”

Автомат, модель которого представлена на рис.1.4, описывает поведение студента и
преподавателей.

Рис. 1.4. 

7