Понятие конечного автомата. Оптимизация автоматов

Тема 1. Понятие конечного автомата. Теория автоматов имеет широкие возможности применения: 1. Проектирование систем логического управления; 2. Обработка текстов и построение компиляторов; 3. Спецификация и верификация систем взаимодействующих процессов; 4. Языки описания документов и объектно-ориентированных программ; 5. Оптимизация логических программ и др. Об этом можно судить по выступлениям на семинаре "Software 2000…" ученых и специалистов. Дуг Росс: "…80 или даже 90 % информатики (Computer Science) будет в будущем основываться на теории конечных автоматов…" Herver Gallaire: "Я знаю людей из "Боинга", занимающихся системами стабилизации самолетов с использованием чистой теории автоматов. Даже трудно себе представить, что им удалось с помощью этой теории. " Brian Randell : "Большая часть теории автоматов была успешно использована в системных программах и текстовых фильтрах в ОС UNIX. Это позволяет множеству людей работать на высоком уровне и разрабатывать очень эффективные программы". 1.1. Понятие конечного автомата Определение. Понятие автомат обычно используется в двух аспектах: 1. Автомат – это устройство, которое выполняет некоторые функции без непосредственного участия человека, например, ЭВМ после загрузки программы и исходных данных решает поставленную задачу без участия человека. 2. Автомат – это математическое понятие обозначающее математическую модель реальных технических автоматов. Здесь автомат представляется в виде «черного ящика» имеющего конечное количество входов, выходов и некоторое множество внутренних состояний. Определение. Автомат называется конечным, если множество его внутренних состояний и множество значений входных и выходных сигналов – конечные множества. Его можно представить в виде некоторого устройства (рис. 1), имеющего входной канал и выходной канал . В каждый из дискретных моментов времени (тактовыми моментами) устройство находится в одном из состояний. По входному каналу в каждый момент времени в устройство поступают входные сигналы. В самом устройстве заданы законы изменения состояния к следующему моменту времени в зависимости от входного сигнала и состояния устройства в текущий момент времени. Выходной сигнал определяется из состояния устройства и входного сигнала в текущий момент времени. Рисунок 1 - Общий вид автомата Обозначим множество входных сигналов через множество , которое называется входным алфавитом, а последовательности входных сигналов – входными словами. Множество состояний автомата обозначим через множество . Через обозначим множество выходных сигналов , которое называется выходным алфавитом, а последовательности выходных сигналов - выходными словами. Функция называется функцией переходов. Функций называется функцией выходов. Таким образом, работу автомата можно описать следующим образом. Устройство, находящееся в одном из состояний воспринимает на входе один из сигналов , после чего на выходе выдает один из сигналов и до поступления нового входного сигнала переходит в другое состояние . Определение. По виду функции выхода автоматы делятся на автоматы Мили и автоматы Мура. Выход автомата Мили зависит от входа и состояния, тогда как выход автомата Мура зависит только от состояния. Иначе говоря, для автомата Мили , для автомата Мура . 1.2. Виды представления автоматов. 1.2.1. Графическое представление. Одним из способов задания автомата является диаграмма переходов-выходов. Это ориентированный граф, вершины которого соответствуют состояниям автомата, а дуги – переходам между состояниями автомата. Если по символу автомат переходит из состояния в состояние , то дуга направляется от вершины к вершине и помечается символом . Если автомат является автоматом Мили, то дуга помечается еще и символом . На диаграмме автомата Мура символ выходного алфавита указывается прямо в вершине, соответствующей связанному с ним состоянию. 1.2.2. Табличный способ представления автомата. Из определения автомата Мили следует, что его всегда можно представить в виде таблицы переходов с двумя входами, содержащей строк и столбцов, где на пересечении столбца и строки стоят значения функций и (см. таб. 1). Таблица 1 - Таблица переходов (управляющая таблица) для автомата Мили x q … … ; … ; … ; … … … … … … ; … ; … ; … … … … … … ; … ; … ; Табличный способ представления автомата Мура строится таблица переходов, которая слева дополняется столбцом, в котором для каждого состояния указывается соответствующий ему выходной символ (см. таб.2). Таблица 2 - Таблица переходов (управляющая таблица) для автомата Мура x q … … … … … … … … … … … … … … … … … … … … … … Такие таблицы так же называют управляющими таблицами. 1.2.3. Представление автомата системой булевых функций. Алгоритм задания конечных автоматов системой булевых функций. 1. Находим число разрядов в двоичном представлении чисел , и (количества входных символов, количества состояний и количества выходных сигналов). Пусть это числа , и . Очевидно, что , , . 2. Кодируем все элементы множеств , и . Количество строк в этой таблице равно , количество столбцов , первые столбцов соответствуют символам входного алфавита, следующие - текущему состоянию. Затем в таблице (см. таб. 3) располагаются столбцов, соответствующих следующему состоянию, и столбцов, соответствующих выходному символу. Закодированные элементы входного алфавита и множества состояний располагаются в лексикографическом порядке (в порядке возрастания их десятичных номеров). Таблица 3 3. Правая часть закодированной таблицы (см. таб. 3) заполняется в соответствии с автоматной таблицей. Если в строке в первых столбцах записан двоичный код символа и состояния, то в последующих столбцах записывают двоичный код состояния и выходного символа . Если хотя бы одно из чисел m , или не является степенью числа 2, то правые части некоторых строк могут оказаться незаполненными. В этом случае их доопределяют произвольным образом. Обычно функции доопределяют таким образом, чтобы минимальные ДНФ полученных функций имели наименьший ранг. 4. По правой части закодированной таблицы состояний выписывают полностью определенную систему булевых функций . Замечание. Кодирование входных символов и состояний можно осуществлять различными способами. Доопределение частично определенных функций также производится неоднозначно. В связи с этим один и тот же автомат может быть задан различными системами булевых функций. 1.2.4. Каноническое представление автомата. На вход автомата в моменты времени последовательно поступают входные символы. Пусть эти символы образуют последовательность входных сигналов , где - символ, поступивший на вход автомата в момент времени . Автомат в этот момент времени находится в состоянии . Под воздействием входного сигнала автомат перейдет в состояние и выдаст выходной сигнал . Величины , , и связаны следующими уравнениями: (1) Определение. Уравнения (1) называются каноническими уравнениями автомата. Чтобы задать канонические уравнения конкретного автомата, сначала его задают системой булевых функций, записанной в координатной форме: (2) Функции в уравнениях (2) задают формулами и как правило, представляют минимальными ДНФ или многочлена Жегалкина. 1.2.5. Представление автомата в виде формул переходов. Пусть задано множество логических условий , принимающих значения из булева множества , и множество микроопераций . Под микрооперацией будем понимать единый неделимый акт обработки информации. Микрокоманда (или оператор) есть некоторый набор микроопераций. Пусть задано множество операторов , где – начальный и – конечный операторы. Рассмотрим произвольный оператор . Определение. Формула перехода из оператора – это выражение вида , где – булевы функции, зависящие от переменных множества логических условий . называется функцией перехода от оператора к оператору . Некоторые из этих функций могут быть равны нулю, и никакие две из них не могут принимать значение единицы на одном наборе значений переменных. Как правило, функции перехода являются ортогональными элементарными конъюнкциями. Слева от знака «» в данной формуле находится оператор, который выполняется в текущий момент времени (такт), справа – операторы, один из которых, в зависимости от значений логических условий, выполнится на следующем такте. Формула означает, что после оператора на следующем такте выполняется оператор (т. е. происходит переход к оператору из оператора ), если . Для конечного оператора формулы перехода, естественно, не существует. Множество формул перехода для операторов образует систему формул перехода (СФП). Замечание. Очевидно, что систему булевых функций и каноническое уравнение удобно применять и к автомату Мили и к автомату Мура, а формулы переходов - для автомата Мура. 1.2.6. Представление автомата в виде граф-схемы алгоритма Определение. Граф-схема алгоритма (ГСА) – это ориентированный слабосвязный граф, содержащий одну начальную вершину , одну конечную вершину , и множество условных вершин, и множество операторных вершин (рис. 2). Рисунок 2 - Виды вершин ГСА Вершины ГСА удовлетворяют следующим условиям: А) из начальной вершины исходит одна дуга, в начальную вершину не заходит ни одной дуги; Б) в конечную вершину заходит не менее одной дуги, из конечной вершины не исходит ни одной дуги; В) в операторную вершину заходит не менее одной дуги, из операторной вершины исходит одна дуга; Г) в условную вершину заходит не менее одной дуги, из условной вершины исходит две дуги, помеченные символами 0 и 1. В каждой условной вершине записывается один из элементов множества логических условий. В каждой операторной вершине записывается микрокоманда. ГСА удовлетворяет следующим условиям: А) каждая вершина графа лежит по крайней мере на одном пути, соединяющем начальную вершину с конечной; Б) одна из исходящих дуг условной вершины может заходить в эту же вершину (такие вершины называются ждущими, или возвратными); В) исходящие из операторных вершин дуги не могут заходить в эти же вершины. Переход от СФП к ГСА Пусть алгоритм задан системой формул переходов. Рассмотрим построение граф-схемы алгоритма. Пусть задана формула переходов вида , на ГСА она изображается так, как показано на рис. 3. Рисунок 3 - Переход между вершинами ГСА Пусть задана формула переходов вида , на ГСА она изображается так, как показано на рис. 4. Рисунок 4 - Изображение на ГСА формулы перехода Справочно. Разложение по Шеннону булевой функции по переменной называется . Пример. Для функции получить разложение по Шеннону по переменной . Пусть теперь задана формула перехода общего вида / Разложим ее правую часть по Шеннону по переменной, которая встречается во всех функциях перехода , получим формулу вида , где , – подформулы вида . Соответствующая разложению часть диаграммы выглядит так, как показано на рис. 5. Рисунок 5 - Граф после разложения по Шеннону Если, например, , то вершина является ждущей: исходящая дуга, помеченная нулем, заходит в эту же вершину. Если , то часть диаграммы, обозначенная через , представляет собой операторную вершину . Иначе разложим подформулу по очередной переменной, нарисуем в диаграмме на месте условную вершину, помеченную этой переменной, и продолжим разложение, если это необходимо. Так действуем до тех пор, пока коэффициенты разложения не будут представлять собой микрокоманды. Таким образом, мы построим подграф, соответствующий формуле перехода. Объединив подграфы для всех формул перехода в один граф, получим ГСА. Следует отметить, что если одна и та же подформула встречается в нескольких формулах перехода, ее можно нарисовать лишь один раз и показать переходы к ней с помощью дуг. Переход от ГСА к автомату Мура Пусть задана ГСА. Построим автомат , реализующий данный алгоритм. Здесь входной алфавит – булево пространство , выходной алфавит – булево пространство . Мы будем описывать входные и выходные сигналы на языке элементарных конъюнкций. Внутренний алфавит , функции переходов и выходов строятся по-разному для автоматов Мура и Мили. Для автомата Мура алгоритм перехода от ГСА к графическому представлению автомата следующий: А) отметка ставится на дуге, исходящей из начальной вершины, и на дуге, заходящей в конечную вершину; Б) отметки ставятся около операторных вершин; В) отметки ставятся на дугах, заходящих в ждущие вершины. С состоянием , расположенным на графе около операторной вершины, связываем выход – множество микроопераций, записанных в этой вершине. Для состояния и состояний, связанных со ждущими вершинами, функция выхода есть пустое множество микроопераций. Автомат переходит из состояния в состояние под воздействием сигнала , который формируется следующим образом: А) Находится очередной простой путь, соединяющий и и не содержащий отметок других состояний. Б) По выбранному пути составляется элементарная конъюнкция: если путь проходит через условную вершину , то входит в конъюнкцию. При этом если исходящая из дуга помечена символом 1, то входит в конъюнкцию без инверсии, иначе входит в конъюнкцию с инверсией. Если путь не проходит ни через одну условную вершину, конъюнкция равна единице. В) Составляется дизъюнкция всех таких элементарных конъюнкций – это функция перехода , т. е. . Переход от ГСА к автомату Мили В случае автомата Мили отметки состояний ставятся: А) отметка ставится на дуге, исходящей из начальной вершины, и на дуге, заходящей в конечную вершину; Б) отметки ставятся на дугах, исходящих из операторных вершин; В) отметки ставятся на дугах, заходящих в ждущие вершины. Заметим, что если дуги, исходящие из двух операторных вершин, заходят в одну вершину, отметка ставится после объединения этих дуг. Если же в одну вершину (не конечную) заходят дуги, исходящие из операторной и условной вершины, отметка ставится до объединения этих дуг. Если за операторной вершиной следует ждущая, отметка ставится после объединения дуг, исходящих из этих вершин. Все сказанное проиллюстрировано на рис. 6. Так как одна и та же вершина может следовать за несколькими операторными вершинами, в общем случае число состояний в автомате Мили меньше, чем число состояний в эквивалентном ему автомате Мура. Рисунок 6 - Отметки для ГСА автомата Мили 1.3. Примеры автоматов. Пример 1. Построение автомата. Автомат, описывающий поведение «умного» отца. Опишем поведение отца, сын которого учится в школе и приносит двойки и пятерки. Отец не хочет наказывать сына каждый, как только сын получает двойку, и выбирает более тонкую тактику воспитания. Зададим такой автомат графом, в котором вершины соответствуют состояниям, а дуга из состояния в состояние , помеченное , проводится тогда, когда автомат из состояния под действием входного сигнала переходит в состояние с выходной реакцией . Граф автомата Мили, моделирующего умное поведение родителя, представлен на рис 7. Этот автомат имеет четыре состояния , два входных сигнала и выходные сигналы , которые будем интерпретировать как действия родителя следующим образом: - наказывать; - ругать сына; - успокаивать сына; - надеяться; - радоваться; - ликовать. Рисунок 7 Сына, получившего одну и ту же оценку – двойку, ожидает дома совершенно различная реакция отца в зависимости от предыстории его учебы. Например, после третьей двойки подряд в истории сына накажут, а в истории будут успокаивать и т.д. Таблица 4 – Таблица переходов для примера 1 Пример 2. Система булевых функций, каноническое уравнение. Пусть автомат задан таблицей 00 , 0 , 1 01 , 1 , 0 10 , 1 , 0 11 , 0 , 1 Графическое представление: Система булевых функций. ; ; . Составим таблицу, содержащую строк и столбцов. Коды входных и выходных символов совпадают с их двоичным значением, состояний - с номером: Входной символ Текущее состояние Следующее состояние Выходной символ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Таким образом, автомат задается булевыми функциями: Для получения канонических уравнений данного автомата представим полученные в предыдущем пункте функции в виде минимальных ДНФ: Пример 3. Система формул переходов. Пусть количество логических условий и количество микроопераций . Рассмотрим СФП для шести операторов (включая начальный оператор): ; ; ; ; ; ; , , , , . Из формул следует, что, например, после выполнения оператора при , и произвольных значениях остальных переменных логических условий на следующем такте выполняется оператор (т. е. микрооперации ), а при , выполняется оператор (микрооперации ). При не происходит перехода ни к какой микрокоманде, это означает, что реализующее алгоритм дискретное устройство не выполняет никаких микроопераций, пока на некотором такте на входе не появится единица. После выполнения оператора на следующем такте происходит безусловный переход к оператору , т. е. оператор выполняется при любых значениях переменных . Пример 4. Система формул переходов. Для автомата Мура, состоящего из входных сигналов , состояний и выходными сигналами с таблицей переходов Выходной символ a b c d Y1 Z1 Z1 Z2 Z3 Z1 Y2 Z2 Z2 Z2 Z2 Z2 Y2 Z3 Z3 Z2 Z3 Z3 Y3 Z4 Z4 Z4 Z4 Z4 Закодируем входные сигналы в двоичном коде входные сигналы следующим образом: a b 1 c 1 d 1 1 Выпишем формулы переходов: Сократив, получаем Пример 5. Построение ГСА по СФП. Рассмотрим СФП из предыдущего примера: ; ; ; ; ; ; , , , , . В первой формуле переменная встречается только без инверсии, значит, вершина x1 является ждущей. Разложим правую часть этой формулы по переменной x1. Разложим по Шеннону также остальные формулы, каждый раз выбирая переменную, которая встречается во всех функциях перехода: ; ; ; ; ; . Здесь подчеркнуты одинаковые подформулы. Соответствующая ГСА показана на рис. 8. Рисунок 8 - Граф-схема алгоритма Пример 6. Построение автомата Мура по ГСА. Рассмотрим ГСА, полученную в предыдущем примере (пример 5). Расставим отметки состояний. Исходящая из начальной вершины дуга заходит в ждущую вершину, значит, в данном случае достаточно одной отметки (рис. 9). Рисунок 9 - ГСА с отметками для автомата Мура Здесь отметки поставлены около операторных вершин , а микрокоманды заменены соответствующими множествами микроопераций. Далее построим граф переходов-выходов автомата. Получили, что автомат Мура состоит из шести состояний. Функции выхода , и т. д. Найдем функцию переходов . Состояния и соединяет один простой путь, проходящий через вершины (дуга помечена единицей) и (дуга помечена нулем), значит, . Также находятся остальные функции переходов. Диаграмма переходов-выходов автомата показана на рис. 10. Рисунок 10 - Граф переходов автомата Мура Пример 7. По ГСА построить автомат Мили. Для ГСА из примера 5 отметки состояний расставляются следующим образом (см. рис. 11). Число состояний здесь на два меньше, чем в эквивалентном автомате Мура. Функция переходов автомата Мили находится так же, как и для автомата Мура. Функция выходов находится следующим образом: если простой путь, соединяющий состояния и , заканчивается операторной вершиной, то функция выхода, соответствующая этому пути, есть множество записанных в операторной вершине микроопераций, иначе функция выхода есть . Рисунок 11 - ГСА с отметками для автомата Мили Диаграмма переходов-выходов автомата Мили показана на рис. 12. Рисунок 12 - Граф переходов автомата Мили Пример 8. Программная реализация. Пусть автомат представлен в виде графа на рис. 13. Условием завершения данного автомата является достижение начального состояния (состояние А). Текущее состояние хранится в переменной state. В теле цикла на каждой итерации (каждом такте) производится чтение входных сигналов, после чего на основе текущего состояния и считанных значений формируются и выводятся значения выходных сигналов автомата. Рисунок 13 char state = ’A’ ; do { bool in1 , in2 ; char out ; get_input(in1 , in2 ); switch ( state ) { case ’A’ : out = in1 ? ( in2 ? ’c ’ : ’d ’ ) : ( in2 ? ’b ’ : ’a ’ ); state = ( in1 && ! in2 ) ? ’C’ : ’B’ ; break; case ’B’ : out = in1 ? ( in2 ? ’b ’ : ’d ’ ) : ( in2 ? ’c ’ : ’a ’ ); state = ! in2 ? ’C’ : ( in1 ? ’B’ : ’A’ ); break; case ’C’ : out = in1 ? ( in2 ? ’c ’ : ’a ’ ) : ( in2 ? ’e ’ : ’d ’ ); state = in2 ? ’B’ : ( in1 ? ’A’ : ’C’ ); break; }; put_output(out ); } while ( state != ’A’ ) Контрольные вопросы 1. Какие уравнения называются каноническими уравнения конечного автомата? 2. Как построить каноническое уравнение конечного автомата? 3. Изложите алгоритм задания конечного автомата системой булевых функций. 4. Как строится диаграмма Мура? 5. Как строится диаграмма Мили? 6. Укажите способы задания конечного автомата с кратким описанием. 7. Что включает в себя понятие конечный автомат? 8. Опишите принцип работы конечного автомата. 9. Чем отличается автомат Мили от автомата Мура при графическом представлении? 10. Чем отличается автомат Мили от автомата Мура при табличном представлении? 11. Чем отличается работа автомата Мили от работы автомата Мура? 12. Опишите алгоритм построения графа перехода автомата Мили по его табличному представлению. Приведите пример. 13. Опишите алгоритм построения графа перехода автомата Мура по его табличному представлению. Приведите пример. 14. Опишите алгоритм построения табличного представления автомата Мили по его графическому представлению. 15. Опишите алгоритм построения табличного представления автомата Мура по его графическому представлению. 16. Чем отличается система формул переходов от системы булевых функций? 17. Чем отличается система формул переходов от канонического представления автомата? 18. Как связаны система формул переходов и закодированная в двоичном представлении таблица переходов? 19. Как связаны система булевых функций и закодированная в двоичном представлении таблица переходов? 20. Опишите алгоритм задания конечных автоматов булевыми функциями. 21. Что такое каноническое представление автомата? 22. Каким образом доопределяются недостающие пустые строки таблицы переходов? 23. Покажите на примере программную реализацию автомата Мили. 24. Покажите на примере программную реализацию автомата Мура. Тема 2. Оптимизация автоматов. 2.1. Терминология. Определение. Если в рабочей зоне управляющей таблицы нет пустых клеток, то автомат называется полностью определенным. В противном случае автомат называется не полностью определенным. Определение. Историей работы конечного автомата без памяти для данной входной цепочки называется упорядоченная (по моменту дискретного времени) совокупность троек значений где: - момент дискретного времени; - текущий входной символ; - текущее состояние. Определение. Автомат, реализующий одну и ту же работу при каждом запуске конкретной цепочки называется детерминированным. Определение. Недетерминированным конечным автоматом называется автомат, который может отрабатывать разные последовательности переходов из состояния в состояние при различных запусках для одной и той же входной цепочки символов. Определение. Недетерминированностью первого рода называется наличие хотя бы одного перехода по пустой цепочке символов в рабочее состояние. Определение. Недетерминированностью второго рода называется наличие в управляющей таблице клеток, содержащих два или более номера состояния (или столбцов, помеченных одним и тем же символом, но не являющихся идентичными). В графе состояний и переходов это соответствует дугам, выходящим из одной вершины, помеченным одним и тем же символом, но ведущим в разные вершины. Таким образом: Определение. Недетерминированный конечный автомат состоит из: 1. конечного множества состояний ; 2. конечного множества входных символов ; 3. одного начального состояния ; 4. множества заключительных (допускающих) состояний ; 5. функций переходов , аргументами которой являются состояние из и входной символ из , а значением – некоторое подмножество множества . Определение. Детерминированный конечный автомат состоит из: 1. конечного множества состояний ; 2. конечного множества входных символов ; 3. одного начального состояния ; 4. множества заключительных (допускающих) состояний ; 5. функций переходов , аргументами которой являются состояние из и входной символ из , а значением – один из элементов множества . Замечание. Нетрудно заметить, что недетерминированный конечный автомат может находится сразу в нескольких состояниях одновременно, а детерминированный конечный автомат всегда находится только в одном состоянии. Определение. Два стояния называются эквивалентными, если дальнейшее поведение автомата в первом состоянии совпадает с дальнейшим поведением автомата во втором состоянии. Таким образом у двух эквивалентны состояний которых строки в управляющей таблице либо полностью совпадают, либо различаются только переходами друг на друга. Любую пару эквивалентных состояний всегда можно заменить одним состоянием без потери функциональности автомата. Пример. Состояния 2 и 3 автомата, представленного на рис. 14, эквивалентны. Рисунок 14 - Эквивалентность состояний Определение. Недостижимым называется такое состояние автомата, в которое не существует ни одного пути из начального состояния в графе состояний переходов. Определение. Тупиковым называется состояние, из которого не существует ни одного пути в какое-либо конечное состояние. Как тупиковые, так и недостижимые состояния в определенном смысле являются лишними. Если удалить эти состояния вместе с всеми переходами – как входящими, так и выходящими из них, то будет получен автомат, эквивалентный исходному. Определение. Оптимальным автоматом в множестве эквивалентных называется полностью определенный детерминированный автомат, управляющая таблица которого имеет наименьшее количество клеток. Оптимальный автомат удовлетворяет следующим условиям: 1. Множества символов, помечающие столбцы управляющей таблицы, попарно не пересекаются. 2. Автомат не содержит недетерминированностей первого рода. 3. Автомат не содержит недетерминированностей второго рода. 4. Автомат не имеет тупиковых состояний. 5. Автомат не имеет недостижимых состояний. 6. Все рабочие состояния попарно не являются эквивалентными. 7. В рабочей зоне управляющей таблице нет одинаковых столбцов. 8. В рабочей зоне управляющей таблице нет пустых клеток. 2.2. Алгоритм. Преобразование недетерминированного неоптимального автомата в детерминированный оптимальный Алгоритм преобразования можно охарактеризовать последовательной проверкой критериев оптимальности и детерминированности с последующим устранением несоответствий. Рассмотрим некоторые алгоритмы. Более подробно и все алгоритмы можно посмотреть, например, в [9]. 2.2.1. Алгоритм. Критерий 1. Устранение пересечений множеств символов разметки столбцов управляющей таблицы. 1. Если в таблице у нескольких столбцов есть одинаковые заголовки, эти столбцы следует объединить. При этом может возникнуть недетерминированность второго рода. 2. Добавить в таблицу по одному пустому столбцу для каждого символа из используемой таблицы кодировки, отсутствующему в заголовках существующих таблиц. В результате в таблице образуется столько столбцов, сколько символов есть в используемой системе кодирования плюс один столбец, помеченный обозначением пустой цепочки символов. Применительно к представлению автомата графом состояний и переходов это преобразование состоит в тома, что каждая дуга, помеченная более чем одним символом, превращается в параллельных дуг, каждая из которых помечена в точности одним символом и ведет в ту же самую вершины, что и исходная дуга. 2.2.2. Алгоритм. Удаление тупиковых состояний (критерий 4). Цель. Найти все тупиковые состояния, если они есть. Для этого необходимо определить списки достижимых финальных состояний для каждого рабочего состояния. После этого удалить тупиковые состояния. Шаг 1. С каждой строкой управляющей таблицы сопоставляется список (в начальный момент – пустой) достижимых финальных состояний, в которые есть переходы из данной строки. Шаг 2. Начиная с нулевой, просматриваются все строки таблицы. Шаг 3. В каждой строке (пусть ее номер ) просматриваются все клетки. Шаг 4. Если клетка не пуста и содержит номер финального состояния, то этот номер добавляется к списку , если его нет в этом списке. Шаг 5. Если клетка не пуста и содержит номер рабочего состояния , , то все элементы списка финальных состояний строки добавляются в список финальных состояний строки (естественно, если их нет в списке ). Шаг 6. Если была просмотрена последняя строка рабочей зоны и в процессе просмотра изменился хотя бы один список , то нужно вернуться к шагу 2, иначе процесс завершается. Все состояния, для которых списки достижимых финальных состояний пусты, являются тупиковыми и их следует удалить. Для этого необходимо: Шаг 7. Удалить из всех клеток таблицы все переходы в выявленные тупиковые состояния; Шаг 8. Удалить строки тупиковых состояний из управляющей таблицей. В графе состояний и переходов это преобразование состоит в замене всех фрагментов вида На фрагменты следующего вида Очевидно, что в результате преобразования будет получен автомат, эквивалентный исходному, поскольку любая история работы преобразованного автомата может быть реализована исходным. Удаление всех тупиковых состояний может привести к образованию эквивалентных состояний, которые в исходном автомате таковыми не являлись. После удаления всех тупиковых состояний необходимо перейти к удалению недостижимых состояний. 2.2.3. Алгоритм. Удаление недостижимых состояний (критерий 5). Цель. Найти все недостижимые состояния, если они есть. Затем их удалить. Шаг 1. С каждой строкой рабочей зоны управляющей таблицы (кроме нулевой строки) сопоставляется отметка «недостижима», а с нулевой строкой – «достижима». Шаг 2. Начиная с нулевой строки просматриваются все «достижимые» строки. Шаг 3. В каждой строке просматриваются все клетки, и если в клетке находится номер рабочего состояния , то значение отметки строки изменяется на значение «достижима». Шаг 4. Если просмотрена последняя строка таблицы и хотя бы для одной строки отметка со значения «недостижима» изменилась на значение «достижима» - возвращение к шагу 2, иначе завершение процесса. Шаг 5. Все строки, отметка которых имеет значение «недостижима», следует удалить из таблицы. В графе состояний и переходов это преобразование состоит в замене всех фрагментов вида на фрагменты . Очевидно, что в результате такого преобразования будет получен автомат, эквивалентный исходному, поскольку любая история работы преобразованного автомата может быть реализована и исходным автоматом, но не наоборот. Удаление недостижимых состояний может привести к образованию эквивалентных состояний, которые в исходном автомате таковыми не являлись. После удаления всех недостижимых состояний необходимо перейти к слиянию эквивалентных состояний. 2.2.4. Алгоритм. Слияние эквивалентных состояний (критерий 6). Для обнаружения эквивалентных состояний необходимо просмотреть все возможные пары строк рабочей зоны управляющей таблицы. Если найдена пара таких строк (пусть будут номера строк и ), содержимое которых полностью совпадает или различается в клетках одного и того же столбца только переходами внутри этой пары (т.е. парами переходов вида { и } или { и }, или { и } или { и }, то: 1. Удалить любую из них (например, строку ) из таблицы; 2. Во всех клетках остальных строк таблицы заменить переходы в удаленное состояние переходами в оставленное состояние ; 3. Вернуться к выполнению данного алгоритма. Заметим, что любое такое преобразование может привести только к нарушению критерия 6. Данное преобразование порождает автомат, эквивалентный исходному, т.к. 1. Это преобразование не влияет как на истории работы до момента перехода в состояния или исходного автомата, полученного в результате преобразования. 2. Начиная с этих моментов для любой входной последовательности символов оба автомата обязательно реализуют совершенно одинаковые остатки историй работы. 3. После обнаружения и слияния всех множеств эквивалентных состояний перейти к алгоритму слияния одинаковых столбцов. 2.4.5. Алгоритм. Слияние одинаковых столбцов (критерий 7). Просмотреть попарно все столбцы управляющей таблицы. Если найдется пара одинаковых столбцов, помеченных множествами символов и , то: 1. Заголовок одного из этих столбцов заменить на объединение множеств и ; 2. Удалить другой столбец. 3. Вернуться к выполнению данного алгоритма. Это преобразование не может привести к нарушению ни одного из критериев. В графе состояний и переходов это преобразование состоит в объединении параллельных дуг и их разметок. При использовании управляющей таблицы, столбцы которой помечены множествами символов, программа, моделирующая поведение конечного автомата, обязана выполнять преобразование кода каждого входного символа в индекс столбца таблицы. Такое преобразование обычно производится с использованием вспомогательной одномерной таблицы, называемой транслитератором. Транслитератор – это одномерный целочисленный массив. Каждый элемент этого массива содержит индекс столбца управляющей таблицы для символа, код которого рассматривается как индекс элемента. 2.3. Примеры. Пример 1. Недетерминированный конечный автомат представлен на рис. 15. В данном автомате дуги с отметкой 0 ведут из состояния в состояния и . И при поступлении входного символа 0 в состоянии автомат переходит одновременно в оба состояния и . Рисунок 15 Пример 2. На рис. 16 представлен граф состояний автомата, содержащего недостижимые, тупиковые и эквивалентные состояния. На рис. 17 представлен эквивалентный автомат без недопустимых (состояния 6, 7 и 8), тупиковых (состояния 2 и 3) и эквивалентных (состояния 4 и 5) состояний. Рисунок 16 Рисунок 17 Контрольные вопросы. 1. Что такое эквивалентность автоматов? 2. Что такое история работы конечного автомата? 3. Что такое недетерминированность конечного автомата? 4. Какие бывают виды недетерминированности? 5. Могут ли быть эквивалентными два конечных автомата, имеющие различное количество финальных состояний? Почему? 6. Могут ли быть эквивалентными два конечных автомата, имеющие различное количество рабочих состояний? Почему? 7. Могут ли быть эквивалентными два конечных автомата, имеющие различное количество входных символов? Почему? 8. Могут ли быть эквивалентными два конечных автомата, имеющие различное количество выходных символов? Почему? 9. Что такое недостижимые состояния? 10. Что такое тупиковые состояния? 11. Дайте определение эквивалентных автоматов? 12. Что такое оптимальный автомат? 13. Опишите алгоритм удаления тупиковых состояний. 14. Опишите алгоритм удаления недостижимых состояний. 15. Опишите алгоритм удаления эквивалентных состояний. Тема 3. Применение теории автоматов и ее расширений. Вспомним слова, которые Вы прочитали в начале курса. Теория автоматов имеет широкие возможности применения: 1. Проектирование систем логического управления; 2. Обработка текстов и построение компиляторов; 3. Спецификация и верификация систем взаимодействующих процессов; 4. Языки описания документов и объектно-ориентированных программ; 5. Оптимизация логических программ и др. Об этом можно судить по выступлениям на семинаре "Software 2000…" ученых и специалистов. Дуг Росс: "…80 или даже 90 % информатики (Computer Science) будет в будущем основываться на теории конечных автоматов…" Herver Gallaire: "Я знаю людей из "Боинга", занимающихся системами стабилизации самолетов с использованием чистой теории автоматов. Даже трудно себе представить, что им удалось с помощью этой теории". Brian Randell : "Большая часть теории автоматов была успешно использована в системных программах и текстовых фильтрах в ОС UNIX. Это позволяет множеству людей работать на высоком уровне и разрабатывать очень эффективные программы". Рассмотрим некоторые аспекты на примерах. 3.1. Машина Тьюринга. Структура машины Тьюринга. 1. Управляющее устройство (УУ). Может быть настроено на выполнение одной из множества возможных операций, т.е. находится в одном из состояний, образующих конечное множество . Среди состояний УУ выделяют начальное состояние, обычно обозначенное как и конечное состояние . В состоянии машина Тьюринга находится перед началом работы, а попов в состояние , она останавливается. Работа машины Тьюринга происходит в дискретный момент времени, когда состояния машины рассматриваются на конечном множестве времени отсчетов, называемых тактами машинного времени и обозначаются . 2. Лента. Лента разбита на ячейки, в каждой из которой может быть записан один из символов конечного внешнего алфавита состоящим из сведений, подаваемых в машину и сведений, которые в ней вырабатываются. Среди знаков имеется пустой символ (пробел) . Запись символа в ячейку означает стирание символа находящегося в ней ранее, и ячейка становится пустой. Лента бесконечна в обе стороны, однако ТВ начальный момент времени, как и в любой другой, только конечное число ячеек заполнено непустыми символами, а остальные символы пусты (заполнены символом ). Фактически важна не бесконечность ленты, а возможность записать в нее в любом месте сколь угодное число символов. 3. Устройство обращения к ленте. Представляет собой считывающую и записывающую головку, которая в каждый момент времени , обозревает какую-либо ячейку ленты и в зависимости от символа в этой ячейке и состояния УУ выполняет одно из действий: а) производит запись в ячейку нового символа (может совпадать со старым, может быть пустым символом , т.е. стирать символ), б) сдвигает головку на одну ячейку вправо или влево, при этом УУ переходит в новое состояние. Перечисленные действия в комплексе представляют собой шаг (элементарное действие) машины Тьюринга, которое определяется парой . Детерминированность машины Тьюринга. Машина Тьюринга обладает свойством детерминированности, т.е. последовательность ее шагов определяется следующим образом. Для любого внутреннего состояния и символа алфавита и символа алфавита однозначно задана логическая функция, которая определяет следующее состояние ; символ , который должен быть записан; направление сдвига головки , где - сдвиг влево на одну ячейку, - сдвиг вправо на одну ячейку, - отсутствие сдвига; причем множество называется внутренним алфавитом машины Тьюринга. Таким образом логическая функция машины Тьюринга сопоставляется каждой паре знаков тройку знаков и может быть записана разными способами. Способ 1. Функциональная схема машины Тьюринга. Представляет собой таблицу, строкам которой соответствуют входные символы из множества , столбцам – состояния из множества , на пересечении строк и столбцов записана тройка символов . Способ 2. Система Тьюринговых команд. Множество состоящее из команд вида , знак «» читается «влечет за собой» или «приводит к…». Команда, соответствующая фрагменту функциональной схемы, представленной в первом способе, имеет вид . Способ 3. Диаграмма (граф) переходов. Изображается в виде графа, в котором состояниям машины Тьюринга соответствуют вершины (узлы), а командам – ребра, ведущие из в , на которых записано , например, . Таким образом, машина Тьюринга представляет собой максимально упрощенный вариант вычислительной машины, имеющей одноадресную структуру, с возможностью изменения адреса обозреваемой ячейки только на 1. Поэтому необходимое для процесса вычислений содержание какой-либо ячейки отыскивается путем постепенной проверки всех ячеек подряд до тех пор, пока не будет обнаружена нужная ячейка. Работа Машины Тьюринга. Рассмотрим работу машины Тьюринга на примере. Пусть задана машина Тьюринга с алфавитом и состояниями . Начальное состояние обозначено . Перед началом работы машины Тьюринга на ленту заносится начальная информация (например, пять единиц) и фиксируется начальная обозреваемая ячейка (например, четвертая), сдвиг отсутствует. Информация в этой ячейке отображает начальное состояние машины Тьюринга. Логическая функция рассматриваемой машины Тьюринга описана функциональной схемой Такт 1. Выполняется Тьюрингова команда , т.е. в обозреваемую ячейку записали , перешли в состояние , сдвига головки не произошло. Получили . Такт 2. Выполняется команда . В обозреваемой ячейке остался символ , осталось состояние , Головка сдвинулась вправо. Получили . Ниже представлен результат работы машины Тьюринга (состояние ленты) для данного примера для семи тактов . Конфигурация машины Тьюринга. Конфигурацией машины Тьюринга называется совокупность ее характеристик таких, как внутреннее состояние, состояние ленты (слова, записанного а ленте). Конфигурация обозначается тройкой символов , где - текущее внутреннее состояние, - слово слева от головки, - слово, образованное символом, обозреваемым головкой, и символами справа от него. При этом слева от и справа от нет непустых символов, т.е. либо записано , либо ничего. Пример. Если , а головка обозревает символ , тогда конфигурация машины Тьюринга ,т.е. Стандартная начальная конфигурация обозначается как , где - начальное состояние, а головка обозревает крайний левый символ. Стандартная конечная конфигурация имеет вид , где - конечное состояние и вокруг обозреваемой ячейки пустые символы. Замечание. Нетрудно заметить, что работу машины Тьюринга можно описать последовательностью конфигураций. 3.2. Вероятностный автомат. Вероятностные автоматы отличаются тем, что в них переходы из одного состояния в другое происходят случайным образом, т.е. входной сигнал может вызывать переход из текущего состояния в различные состояния с некоторой вероятностью. Вероятностный автомат может быть задан в виде графа или таблицы переходов, которая принимает вид матрицы переходных вероятностей. На рис. 18 представлен вероятностный автомат. Очевидно, что из вершины графа вероятностного автомата могут выходить несколько дуг, отмеченных одинаковым выходным сигналом. Рисунок 18 - Пример вероятностного автомата Таблица переходов вероятностного автомата имееn вид матрицы переходных вероятностей и составляется для каждого входного сигнала: x=0 x=1 Q0 Q1 Q0 Q1 Q0 1 1 Q0 0.7 0.5 Q1 Q1 0.3 0.5 Из примера видно, что сумма вероятностей переходов в любом состоянии равна 1 или 0 (если состояние недостижимо при данном входном сигнале). Вероятностный автомат может быть реализован в виде системы, состоящей из детерминированного автомата и датчика случайных чисел, который выдает сигналы с заданным распределением вероятностей. В зависимости от состояния и входного сигнала случайное число сравнивается с пороговым значением (в данном случае это величины 0,3 или 0,5). Сигнал с выхода схемы сравнения поступает на дополнительный вход автомата вместе с основным сигналом . Тем самым реализуется вероятностная логика работы автомата. Одним из примеров применения вероятностных автоматов является автомат управления светофорами на перекрестке c автоматическим переключением с красного сигнала на зеленый при появлении автомобиля. Контрольные вопросы 1. Что включает в себя понятие вероятностный конечный автомат? 2. Опишите принцип работы вероятностного конечного автомата. 3. В чем заключается проблема гонок в конечных автоматах? 4. Приведите пример вероятностного автомата в виде графа. 5. Приведите пример вероятностного автомата в табличном виде. 6. Чем вероятностный автомат отличается от обычного автомата? 7. Опишите принцип работы машины Тьюринга. 8. Из чего состоит математическое описание машины Тьюринга. 9. Что такое история работы машины Тьюринга? 10. Кратко опишите способы задания машины Тьюринга. 11. Что такое конфигурация машины Тьюринга? 12. Что такое тьюрингова команда? 13. Функциональная схема машины Тьюринга. 14. Поясните особенности вероятностных автоматов. 15. Как отмечаются дуги вероятностных автоматов? 16. Как составляются матрицы переходов вероятностного автомата? 17. Приведите пример вероятностного автомата. 18. Каким образом реализуется работа вероятностного конечного автомата? Тема 4. Устойчивость автоматов Одной из важнейшей проблемой устойчивой работы автоматов является так называемая проблема «гонок». 4.1. Гонки в автоматах Ранее при рассмотрении процесса работы автоматов принималось, что работа автомата происходит в дискретные моменты времени. При этом считалось, что переходы автомата из одного состояния в другое происходят мгновенно. Это означало, что при изменении входных сигналов соответственно мгновенно изменяются и сигналы на выходе схемы. На практике реальные логические элементы и элементы памяти при изменении входных сигналов изменяют выходные сигналы с некоторой временной задержкой. Важно то, что время задержки сигнала элементами зависит от типа элемента. Кроме того, даже для однотипных элементов время задержки всегда различно, так как различны параметры радиодеталей, из которых составлены элементы. Даже для одного и того же элемента время задержки может меняться при изменении условий работы, например при изменении температуры, напряжения питания и т.д. Наконец, при работе автомата входные сигналы элементов памяти проходят через комбинационные схемы, составленные из различного количества элементов, т.е. с различной задержкой. Если автомат имеет несколько элементов памяти, то сигналы на их выходах меняются не одновременно. Сигнал на выходе элемента памяти, который переключился первым, через линии обратной связи (с выхода элементов памяти на входы схемы формирования состояний) может поступить на входы других элементов памяти и изменить логику их переключения, т.е. логику переходов автомата из одного состояния в другое. Эффект гонок может возникать лишь в случаях, когда переход автомата из одного состояния в другое связан с одновременным переключением нескольких триггеров. Идея противогоночного кодирования заключается в том, что состояния автомата кодируются так, чтобы при любом переходе автомата из одного состояния в другое переключался только один элемент памяти. В настоящее время существуют алгоритмы противогоночного кодирования. Эти алгоритмы связаны с перебором всех возможных переходов автомата и являются довольно громоздкими. Кроме того, реализация таких алгоритмов может потребовать введения дополнительных состояний специально для устранения гонок. Более подробно о противогоночном кодировании можно почитать, например, в [8]. 4.2. «Смерть» автоматов При построении автоматов всегда необходимо учитывать два типа действий. 1. Действия, не затрагивающие данного состояние. 2. Действия, которые не следует допускать во избежание смерти автомата. Рассмотрим на конкретном примере взаимосвязи клиента, магазина и банка. Для простоты предположим, что есть всего один «денежный» файл («деньги»). Клиент может принять решение передать этот файл магазину, который затем обменяет его в банке (точнее, потребует, чтобы банк взамен его выпустил новый файл, принадлежащий уже не клиенту, а магазину) и доставит товар клиенту. Кроме того, клиент имеет возможность отменить свой файл, т.е. попросить банк вернуть деньги на свой счет, причем они уже не могут быть израсходованы. Взаимодействие трех участников ограничено, таким образом, следующими пятью событиями. 1. Клиент может совершить оплату (pay) товара, т.е. переслать денежный файл в магазин. 2. Клиент может выполнить отмену (cancel) денег. Они отправляются в банк вместе с сообщением о том, что их сумму следует добавить к банковскому счету клиента. 3. Магазин может произвести доставку (ship) товара клиенту. 4. Магазин может совершить выкуп (redeem) денег. Они отправляются в банк вместе с требованием передать их сумму магазину. 5. Банк может выполнить перевод (transfer) денег, создав новый, надлежащим образом зашифрованный, файл и переслав его магазину. Во избежание недоразумений участники должны вести себя осторожно. В нашем случае мы предполагаем, что клиенту доверять нельзя. Клиент, в частности, может попытаться скопировать денежный файл и после этого уплатить им несколько раз или уплатить и отменить его одновременно, получая, таким образом, товар бесплатно. Банк должен вести себя ответственно, иначе это не банк. В частности, он должен проверять, не посылают ли на выкуп два разных магазина один и тот же денежный файл, и не допускать, чтобы одни и те же деньги и отменялись, и выкупались. Магазин тоже должен быть осторожен. Он, например, не должен доставлять товар, пока не убедится, что получил за него деньги, действительные к оплате. На рис. 19 участники представлены автоматами. На диаграмме показаны лишь те события, которые влияют на того или иного участника. Например, действие оплата влияет лишь на клиента и магазин. Банк не знает о том, что клиент отправил деньги в магазин; он узнает об этом, когда магазин выполняет действие выкуп. Рисунок 19 - Конечные автоматы, представляющие клиента, магазин и банк Тройка автоматов на рис. 19 отображает поведение участников независимо друг от друга, однако некоторые переходы в автоматах пропущены. Так, сообщение об отмене денег не затрагивает магазин, и если клиент отменяет деньги, то магазин должен оставаться в том же состоянии, в котором находился. Однако согласно формальному определению конечного автомата, если на вход автомата подается X, то он должен совершить переход по дуге с меткой X из текущего состояния в некоторое новое. Следовательно, к каждому состоянию автомата для магазина нужно добавить еще одну дугу с меткой отмена, ведущую в то же состояние. Тогда при выполнении отмены автомат, изображающий магазин, может совершить "переход", который состоит в том, что автомат остается в том же состоянии, в котором и был. Если бы этих дополнительных дуг не было, то автомат, изображающий магазин, "умирал" бы, т.е. он не находился бы ни в каком состоянии, и любые его последующие действия были бы невозможны. Еще одна потенциальная проблема кроется в том, что участники могут, умышленно или случайно, отправить сообщение, не предусмотренное протоколом, и мы не хотим, чтобы это повлекло "смерть" одного из автоматов. Представим, например, что клиент выполнил действие оплата во второй раз, когда магазин находился в состоянии e. Поскольку это состояние не имеет выходящей дуги с меткой оплата, то автомат, изображающий магазин, умрет прежде, чем получит перевод из банка. Итак, к некоторым состояниям автоматов на рис. 19 нужно добавить петли с метками, обозначающими действия, которые следует проигнорировать в этих состояниях. Дополненные таким образом автоматы изображены на рис. 20. Для экономии места дуги с разными метками, имеющие начало и конец в одном и том же состоянии, объединяются в одну дугу с несколькими метками. Рисунок 20 - Полные множества переходов для трех автоматов Контрольные вопросы 1. В чем заключается проблема гонок в конечных автоматах? 2. В каком случае автомата может «умереть»? 3. Что такое «смерть» автомата? 4. Что является причиной гонок в автоматах? 5. В чем проявляется эффект гонок? 6. При каких условиях могут возникать гонки? 7. В чем заключается идея противогоночного кодирования? Заключение. К сожалению, объем курса не позволяет более подробно остановиться на некоторых разделах теории автоматов. Литература 1. Савельев А.Я. Прикладная теория цифровых автоматов: Учеб. Для вузов по спец. ЭВМ / А.Я. Савельев. – М.:Высш. шк., 1987. – 272с.: ил. 2. Рощин А.Г., Половов Р.М. Теория автоматов. Часть II . Автоматы с памятью. Учебное пособие. - М.: МГТУ ГА, 2008. –116 с., табл., ил., лит.: 6 наим. 3. Князьков В.С. Введение в теорию автоматов [Электронный ресурс] / В.С. Князьков, Т.В. Волченская. — 2-е изд. — Электрон. текстовые данные. — М. : Интернет-Университет Информационных Технологий (ИНТУИТ), 2016. — 89 c. — 2227-8397. — Режим доступа: http://www.iprbookshop.ru/73673.html 4. Баранов С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы). – 2-е изд., перераб. и доп. – Лю: Энергия, Ленингр. Отд-ние, 1979. – 232 с., ил. 5. Хопкрофт Д.Э., Мотвани Р., Ульман Д.У. Введение в теорию автоматов, языков и вычислений, 2-е изд.: Пер. с англ.- М.: Издательский до «Вильямс», 2002. – 528 с.: ил. – Парал. тит. англ. 6. Галушкина Ю.И. Конспект лекций по дискретной математике. / Ю.И. Галушкина, А.Н. Марьямов. – М.: Айрис-пресс, 2007. – 176 с. – (Высшее образование). 7. Буркатовская Ю.Б. Теория автоматов: учебно-методическое пособие / Ю.Б. Буркатовская, Е.С. Веремеенко; Национальный исследовательский Томский политехнический университет. – Томск: Изд-во Томского политехнического университета, 2010. – 108 с. 8. Лупал А.М. Теория автоматов: Учеб. пособие / СПбГУАП. СПб., 2000. 119 с.: ил. 9. Малявко А.А. Формальные языки и компиляторы [Электронный ресурс] : учебник / А.А. Малявко. — Электрон. текстовые данные. — Новосибирск: Новосибирский государственный технический университет, 2014. — 431 c. — 978-5-7782-2318-9. — Режим доступа: http://www.iprbookshop.ru/47725.htmlМозговой М.В. Классика программирования: алгоритмы, языки, автоматы, компиляторы. Практический подход. – Спб.: Наука и техника, 2006. – 320 с.: ил. 10. Унучек С.А. Математическая логика [Электронный ресурс] : учебное пособие / С.А. Унучек. — Электрон. текстовые данные. — Саратов: Ай Пи Эр Медиа, 2018. — 239 c. — 978-5-4486-0086-9. — Режим доступа: http://www.iprbookshop.ru/69312.html 11. Хлуденев А.В. Операционное устройство [Электронный ресурс]: методические указания/ Хлуденев А.В.— Электрон. текстовые данные.— Оренбург: Оренбургский государственный университет, ЭБС АСВ, 2003.— 50 c.— Режим доступа: http://www.iprbookshop.ru/51605.html.— ЭБС «IPRbooks» 12. Федотов И.Е. Модели параллельного программирования [Электронный ресурс] / И.Е. Федотов. — Электрон. текстовые данные. — М. : СОЛОН-ПРЕСС, 2012. — 384 c. — 978-5-91359-102-9. — Режим доступа: http://www.iprbookshop.ru/20877.html 13. Дискретная математика: учеб. пособие / сост. В.М. Пестриков, В.С. Дудкин, Г.А. Петров. – СПб.: СПб ГТУРП, 2013. – 136 с. 14. Князьков В.С. Введение в теорию автоматов [Электронный ресурс]/ Князьков В.С., Волченская Т.В.— Электрон. текстовые данные.— М.: Интернет-Университет Информационных Технологий (ИНТУИТ), 2016.— 89 c.— Режим доступа: http://www.iprbookshop.ru/73673.html.— ЭБС «IPRbooks». Оглавление Тема 1. Понятие конечного автомата. 1 1.1. Понятие конечного автомата 1 1.2. Виды представления автоматов. 3 1.2.1. Графическое представление. 3 1.2.2. Табличный способ представления автомата. 3 1.2.3. Представление автомата системой булевых функций. 4 1.2.4. Каноническое представление автомата. 5 1.2.5. Представление автомата в виде формул переходов. 6 1.2.6. Представление автомата в виде граф-схемы алгоритма 8 Переход от ГСА к автомату Мура 11 Переход от ГСА к автомату Мили 12 1.3. Примеры автоматов. 13 Контрольные вопросы 24 Тема 2. Оптимизация автоматов. 25 2.1. Терминология. 25 2.2. Алгоритм. Преобразование недетерминированного неоптимального автомата в детерминированный оптимальный 28 2.2.1. Алгоритм. Критерий 1. Устранение пересечений множеств символов разметки столбцов управляющей таблицы. 28 2.2.2. Алгоритм. Удаление тупиковых состояний (критерий 4). 29 2.2.3. Алгоритм. Удаление недостижимых состояний (критерий 5). 30 2.2.4. Алгоритм. Слияние эквивалентных состояний (критерий 6). 31 2.4.5. Алгоритм. Слияние одинаковых столбцов (критерий 7). 32 2.3. Примеры. 33 Контрольные вопросы. 34 Тема 3. Применение теории автоматов и ее расширений. 34 3.1. Машина Тьюринга. 35 3.2. Вероятностный автомат. 40 Контрольные вопросы 41 Тема 4. Устойчивость автоматов 41 4.1. Гонки в автоматах 42 4.2. «Смерть» автоматов 43 Контрольные вопросы 46 Лабораторные работы. 47 Лабораторная работа 1. «Машина Тьюринга» 47 Лабораторная работа 2. Работа с автоматами Мили и Мура. Часть 1. 50 Лабораторная работа 3. Работа с автоматами Мили и Мура. Часть 2. 52 Заключение. 55 Литература 55