Введение в ТА. Машина Тьюринга

Лекция 1. Введение в ТА. Машина Тьюринга 1. 2. 3. 4. 5. 6. Введение История создания МТ Устройство МТ и пример работы Проблема останова Полнота по Тьюрингу Игра Жизнь – пример Тьюринг-полного вычислителя Знакомство. Теория Автоматов - раздел дискретной математики. Лежит на пересечении математики и информатики. Мы все с вами с точки зрения та окружены автоматами (банкоматы, компьютеры...). ТА - одно из средств проектирования, применяемое в различных сферах. Где применяется: - цифровые устройства -химия - программирование - синтаксические анализаторы Наша задача - научиться пользоваться этим инструментом проектирования. Прежде, чем мы углубимся в теорию автоматов познакомимся с одним из исторических примеров применения автомата при проектировании одного устройства. Машина Тьюринга Автором этого умозрительного устройства является выдающийся английский математик А́ лан Мэ́тисон Тью́ринг, (англ. Alan Mathison Turing; 1912 —1954). Основной период его деятельности пришелся на годы второй мировой войны, поэтому деятельность его как ученого была связана с криптографией, в частности со взломом немецких шифров («Эни́гма» (от нем. Änigma — загадка) — переносная шифровальная машина, использовавшаяся для шифрования и расшифрования секретных сообщений. Более точно, «Энигма» — целое семейство электромеханических роторных машин, применявшихся с 20-х годов XX века.). Несмотря на то, что устройство шифровальной машины было известно, для взлома приходилось перебирать множество комбинаций. Для ускорения этого процесса на основе теоретических выкладок Тьюринга была создана сначала электронно-механическая дешифровальная машина Bombe (1940), а затем полностью электронная вычислительная машина Colossus (1943) – первый программируемый компьютер. Такими были времена зари вычислительной техники, когда вычислять нужно было много, и выигрывал тот, кто сумеет сделать это быстрее всего. Поэтому еще до начала войны мировые ученые стали серьезно заниматься вопросами разработки некоторых универсальных вычислителей, способных решить любую задачу. Понятно, что из-за их универсальности, структура должна быть предельно проста. В связи с этим в 1936 году, в возрасте 24 лет, Тьюринг публикует работу, в которой описывает простые гипотетические устройства, которые впоследствии стали известны как машины Тьюринга. Фон Нейман (один из разработчиков архитектуры первых ЭВМ) признал, что концепция современного компьютера основана на этой работе Алана Тьюринга. Рассмотрим устройство МТ. Поскольку устройство умозрительное, описание его работы немного похоже на описание правил игры. 1 Машина Тьюринга состоит из двух частей: бесконечной ленты (память) и устройства управления. Лента разделена на ячейки, в каждой ячейке может быть записан символ (или она может быть пустой). Например… (рисуем символы на ленте): 2*3 Все возможные символы, которые могут быть на ленте образуют внешний алфавит Z = {□, z1, z2, …, zn} МТ преобразует запись на ленте в соответствии с запрограммированным в УУ алгоритмом решения какой-то конкретной задачи. Например, пусть в нашей МТ записан алгоритм умножения чисел от 0 до 3. То есть наша МТ должна преобразовать запись на ленте в 6. Тогда ее алфавит будет … Для преобразования символов на ленте УУ оснащено ГСЗ, которая располагается над одной из ячеек ленты, и может читать символ и записывать символ в ячейку. Как технически это реализуется – не важно. ГСЗ управляется УУ. Правила его работы следующие. 1) УУ в каждый дискретный момент времени может находиться в одном состоянии из конечного множества Q = {q0, q1, q2, …, qm} (число зависит от конкретной задачи) (начинаем рисовать табличку). Среди них есть начальное (0) и конечное (z) 2) и в каждый дискретный момент времени УУ в qi читает символ zj (в нашем случае она может прочитать цифры от 0 до 3. * и пустой символ – пишем в табличке строки) и в зависимости от состояния и прочтенного символа, - записывать вместо него другой zj’ - и сдвигает ГСЗ на одну ячейку вправо, или влево, или оставляет на месте (R, L, S) - переходит в новое состояние qi'. Например – заполняем табличку с комментариями типа если МТ была в q0 и увидела 0… Такая таблица называется таблицей переходов МТ. Она полностью определяет алгоритм работы конкретной МТ. 1 2 3 * q0 q1 q0, 0,R q1, ,R q2, ,R q3, ,R q4, ,R qz, ,R q2 qz, 0,S qz, 2,S qz, 4,S qz, 6,S q2, ,R q3 qz, 0,S qz, 3,S qz, 6,S qz, 9,S q3, ,R q4 qz q4, ,L q4, ,L q4, ,L q4, ,L qz, ,L 2 По-другому можно изобразить ее в виде графа переходов МТ, где каждому состоянию будет соответствовать вершина, а каждой заполненной клетке – дуга (рисуем). Итак, мы узнали два способа задания алгоритма работы МТ: таблица и граф, чуть позже узнаем третий, а пока посмотрим, как МТ будет работать в соответствии с этим алгоритмом. Пусть ГСЗ в начальный момент времени обозревает ячейку с первым символом (цифрой 2, рисуем ленту). Раз это начальный момент времени, УУ будет находиться в каком состоянии? В начальном q0. Согласно табличке (или графу) МТ в состоянии q0 при виде символа 2 должна… (q0, 2)  (q2, □, R) рисуем ленту и так проходим до конца. Таким образом, в каждый дискретный момент времени МТ выполняет одну из, т.н. Тьюринговых команд: (qi, zj)  (qi, zj, dk) qi,qi’  Q; zj,zj’  Z; dk  D = {L, R, S} Множество всех возможных Тьюринговых команд – третий способ задания алгоритма работы МТ. Его легко получить из графа или таблички. Каждая стрелка на графе или клетка в таблице – команда. Их 21. Так мы узнали 3 способа задания алгоритма работы МТ: 1) таблица переходов 2) граф переходов 3) множество Тьюринговых команд УУ МТ – конечный автомат. Самое интересное – научиться составлять такие таблички для конкретных задачек. Это вам предстоит сделать при выполнении ЛР, некоторым – сегодня. Это – искусство программирования, процесс творческий, чтобы его понять, начнем с простых задачек. 3 Пример 1. Дан алфавит A = {a, b, c}. Приписать к входному слову P букву a: P →P a. ГСЗ над первым символом В чем будет идея решения? Движемся вправо, пока не найдем пустой символ и заменяем его на а и останавливаемся: a b c  q0 q1 q0,a,R q0,b,R q0,c,R q1,a,S Если напишем в последнем случае q0, то по правилам 1ой и последней строк получится бесконечное приписывание a. Пример 2. Дан алфавит A = {a, b, c}. Приписать к входному слову P слово aba: P →P aba. Здесь нужно сделать то же, только в конце пустые символы нужно заменять на разные буквы, поэтому потребуются разные состояния: a b c  q0 q1 q2 q0,a,R q0,b,R q0,c,R q1,a,R q2,b,R q3,a,S 4 Пример 3. Дан алфавит A = {a, b, c}. Написать 0, если входное слово P чётной длины, иначе написать 1. Идея – сдвигаемся влево и каждый раз переключаемся между 2мя состояниями, если встретим пустой символ в первом – значит четное число, во втором – нечетное: a b c  q0 q1,a,R q1,b,R q1,c,R q2,0,S q1 q0,a,R q0,b,R q0,c,R q2,1,S Полнота по Тьюрингу Тьюринг доказал, что подобная машина была бы способна произвести любые математические вычисления, представимые в виде алгоритма. «С помощью машины Тьюринга можно решить любую задачу, которую можно решить алгоритмически». Это утверждение известно под названием тезис Чёрча – Тьюринга (существуют и другие его формулировки). Вычислительная система или язык программирования, который обладает этим свойством называется Тьюринг-полным. Тьюринг-полные Тьюринг-неполные Язык Ассемблера SQL C HTML C++ CSS Java XML JavaScript Python Haskell Для доказательства полноты достаточно промоделировать работу машины Тьюринга на этом вычислителе или языке. Например, доказательством полноты МТ является существование так называемой универсальной МТ, с помощью которой можно промоделировать работу любой другой МТ, при этом набор команд и входные данные первой подаются на вход. Теорема об универсальной машине Тьюринга была предложена и доказана Тьюрингом в 1947 г, она утверждает, что такая машина существует и моделирует другие машины с не более чем квадратичным замедлением (то есть если исходная машина произвела t шагов, то универсальная произведёт не более ct²). 5 Игра «Жизнь» - пример Тьюринг-полного вычислителя Игра «Жизнь» (англ. Conway's Game of Life) — клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году. Джон Хо́ртон Ко́нвей (род. 26 декабря 1937, Ливерпуль) — английский математик, известен в первую очередь как создатель клеточного автомата «Жизнь», однако его вклад в математику очень многообразен и значителен. Занимается теорией конечных групп, теорией узлов, теорией чисел. Джон Конвей заинтересовался проблемой, предложенной в 1940-х годах известным математиком Джоном фон Нейманом, который пытался создать гипотетическую машину, которая может воспроизводить сама себя. Джону фон Нейману удалось создать математическую модель такой машины с очень сложными правилами. Конвей попытался упростить идеи, предложенные Нейманом, и в конце концов ему удалось создать правила, которые стали правилами игры «Жизнь». Имеется размеченная на клетки поверхность (в пределе — бесконечная плоскость). Каждая клетка на этой поверхности может находиться в двух состояниях: быть «живой» или быть «мёртвой» (пустой). Клетка имеет восемь соседей (окружающих клеток). Этот автомат использует понятие соседства по Муру. б) а) Окрестности: а) – фон Неймана, б) – Мура Мы задаем распределение живых клеток в начале игры (первое поколение). Каждое следующее поколение рассчитывается на основе предыдущего по таким правилам (рисуем граф): - в пустой (мёртвой) клетке, рядом с которой ровно три живые клетки, зарождается жизнь; - если у живой клетки есть две или три живые соседки, то эта клетка продолжает жить; в противном случае (если соседей меньше двух или больше трёх) клетка умирает («от одиночества» или «от перенаселённости») Игра прекращается, если - на поле не останется ни одной «живой» клетки - игра зацикливается, то есть картина расположения клеток периодически повторяется или не изменяется совсем. N=3 или N=2 N≠3 и N≠2 1 N≠3 N=3 Пояснение: 1 – состояние «живой», 0 – состояние «мертвый», N – число живых соседей. Задавая различные начальные конфигурации автомата, можно получать различные картины его динамики. Среди всего многообразия возможных картин выделяют фигуры, отличающиеся от остальных своим характерным поведением. 6 Рисунок 4 – Игра «Жизнь» Во-первых, существуют статические конфигурации клеток, не изменяющие своего состояния во времени. Примеры таких конфигураций, состоящих из наименьшего числа живых клеток, приведены на рисунке (последняя – периодическая!). Примеры статических фигур в игре «Жизнь» Некоторые конфигурации автомата являются периодическими. Такие фигуры могут находиться в некотором конечном числе состояний, последовательность которых с некоторым периодом повторяется. Больший интерес представляют двигающиеся фигуры, то есть конфигурации, которые повторяются с некоторым периодом и с некоторым смещением в пространстве. Наиболее известной из таких фигур является «планер» (glider). 7 t=0 t=2 t=1 t=3 t=4 Последовательность состояний планера (можно нарисовать только первый) Существуют и другие движущиеся фигуры, а также фигуры-генераторы планеров (ружья), фигуры-поглотители планеров. Именно планеры являются основой для проведения вычислений (1 = есть планер, 0 = нет планера). Поль Рендель 2 апреля 2000 года создал модель машины Тьюринга с помощью клеточного автомата Джона Хортона Конвея, а 10 февраля 2010 года повторил свой замечательный опыт. В первой модели использовалась решетка 1714 х 1647. Она имела три возможных состояния и могла обрабатывать на ленте памяти три разных символа. В эксперименте 2010 года была создана модель универсальной машины Тьюринга. Возможность моделирования машины Тьюринга с помощью игры «Жизнь» привела к удивительному выводу: игра «Жизнь» имела аналогичные с компьютером возможности. Существуют и другие успешные примеры создания машин Тьюринга с помощью игры «Жизнь», некоторые из них даже получили собственные названия: MRM (Minsky Register Machine) или ее универсальная версия URM, а также CoreWorld, LogiCell и другие. Таким образом было доказано, что игра «Жизнь» является универсальным Тьюрингполным вычислителем. А это означает, что любая вычислительная система, способная моделировать эту игру – Тьюринг-полна. Каждая клетка клеточного автомата – конечный автомат. 8 Лекция 2. Предмет исследования теории автоматов 1. Объекты ТА. 2. Понятие конечного автомата a. Классические КА без выхода b. Автоматы модели Мили c. Автоматы модели Мура 3. КА полностью и частично определенные 4. Задачи ТА. 5. Понятие эквивалентных и минимальных конечных автоматов 6. Минимизация полностью определенных автоматов методом расщепления классов эквивалентных состояний (алгоритм Мура) Объекты ТА На прошлой лекции мы с вами познакомились с МТ. МТ можно назвать самой многофункциональным объектом, изучаемым ТА. Почему? Так как с помощью МТ можно реализовать любой алгоритм. Самым маломощным объектом ТА является логическая (булева) функция. Например, F ( A, B, C , D )  A B C  B D . БФ реализует так называемую комбинационную логику (результат работы функции зависит только от комбинации значений ее аргументов в данный момент времени). Более сложные объекта ТА и МТ в том числе реализуют так называемую секвенциальную (последовательную. от слова sequence - последовательность) логику, так как их реакция на входное значение зависит от значений, подаваемых ранее. БФ может быть реализована в виде МТ с одним состоянием (начальное = конечное). Где на ленте в одной ячейке будет расположено значение аргумента БФ (в виде шестнадцатеричной цифры. например, где каждый разряд соответствует значению аргумента), а МТ вместо него запишет ответ. Наиболее известными устройствами, основанными только на реализации БФ являются, например, сумматор, шифратор, дешифратор, мультиплексор и демультиплексор – элементарные части ядра любого ЭВМ. Существуют и другие объекта ТА: 9 Конечные автоматы Наибольший практический интерес представляют конечные автоматы. И на прошлой лекции мы познакомились с двумя примерами конечных автоматов (УУ МТ и клетка игры «Жизнь»). Что у них было общего? Возможность построения логики работы в виде графа, а на графе - состояния и переходы между ними. Это и есть суть конечных автоматов. Например, нарисуем конечный автомат (рисуем без выходных символов): Дадим строгое определение. Конечный автомат – модель дискретного устройства, имеющего один вход и один выход и в каждый момент времени находящегося в одном состоянии из конечного множества возможных. zi АА wj Конечный автомат полностью определяется шестеркой объектов: S = (A, Z, W, δ, λ, a0), A = {a0, a1, …, am, …, aM} – множество состояний (алфавит состояний); a0  A – начальное состояние автомата (то есть живая клетка или мертвая в начале игры). Z = {z1, …, zf, …, zF} – множество входных символов (входной алфавит); W = {w1, …, wg, …, wG} – множество выходных символов (выходной алфавит); δ: A × Z → A – функция переходов; каждой паре (am, zf) она ставит в соответствие состояние перехода as, т. е. as = δ(am, zf); ее можно задать в виде графа (как у нас, действительно, каждой паре … по графу можно определить соответствующий переход) или еще как можно? в виде таблички a0 a1 a2 a3 z1 a0 a2 a3 a2 z2 a3 a0 a1 a1 Такая таблица называется таблицей переходов конечного автомата. Для определения функции выходов λ наиболее часто используются три варианта: 1) Классический конечный автомат (без выходных символов) (Finite Automation в JFLAP) W=Ø λ: не определена В этом случае автомат должен иметь множество заключительных, или конечных состояний F ⊂ A; 10 Принято полагать, что любой конечный автомат начинает работу в состоянии a0, последовательно считывая по одному символу входного слова (цепочки входных символов). Считанный символ переводит автомат в новое состояние в соответствии с функцией переходов. Если по окончании входного слова P автомат (1) оказался в конечном состоянии, то говорят, что конечный автомат допустил слово P. Этот тип автоматов используется при синтаксическом анализе текста программы в компиляторах (проверка синтаксиса). 2) Автомат Мили. (Mealy Machine в JFLAP) λ: A × Z → W каждой паре (am, zf) она ставит в соответствие выходной символ wg, т. е. wg = λ(am, zf); ее можно задать на графе переходов или в табличке или в виде отдельной таблички a0 a1 a2 a3 z1 a0/w1 a2/w2 a3/w1 z2 a3/w2 a0/w2 a1/w2 Назван именем Джорджа Мили (George H. Mealy) (1927 – 2010), американского математика и специалиста в области информатики, предложившего этот автомат в 1955 году в статье «A Method for Synthesizing Sequential Circuits» Является родоначальником концепции модульного программирования (когда программа делится на небольшие независимые друг от друга модули). Такие программы удобнее тестировать и отлаживать. УУ МТ у нас представляло собой автомат Мили. 3) Автомат Мура. (Moore Machine в JFLAP) Автомат Мура назван в честь описавшего его свойства американского профессора математики и информатики Эдварда Ф. Мура (Edward F. Moore) (1925 — 2003), предложившего этот автомат в 1956 году в статье «Gedanken-experiments on Sequential Machines» (Мысленные эксперименты с секвенциальными машинами). Вместе с Джноном Конвеем занимался клеточными автоматами. Используемый в игре «Жизнь» тип соседства называется соседством Мура. Мур доказал теорему садах Эдема для клеточных автоматов (садами Эдема называются конфигурации живых клеток, которые невозможно получить в результате эволюции никакой исходной конфигурации). (Теорема утверждает, что сады Эдема существуют только в тех автоматах, в которых существуют близнецы. Две конечные конфигурации клеточного автомата называются близнецами (англ. twins), если их эволюции, начиная со следующего поколения, полностью совпадают.) Клетка игры жизнь представляет собой автомат Мура. 11 В клетке игры жизнь не было явного выходного символа, но если задуматься, поскольку входным символом является число живых соседей, на выходе мы должны иметь состояние клетки, чтобы иметь возможность сформировать входные сигналы клеток на следующем такте игры. Получаем автомат, выходной сигнал которого не зависит от входного сигнала в текущий момент времени, а зависит только от состояния. λ: A → W каждому состоянию (am) функция ставит в соответствие выходной символ wg, т. е. wg = λ(am); для нашего примера просто wg = am Нарисуем пример автомата Мура. w1 w2 w1 w2 a0 a1 a2 a3 z1 a1 a2 a1 a3 z2 a2 a3 a0 a2 Таким образом, существует два способа описания КА: граф и таблица. Существует еще матрица переходов. Полностью и частично определенные конечные автоматы Автомат Мура у нас получился полностью определенный. а автомат Мили – нет. Почему? Конечный автомат называется частично-определенным, если не для всех пар (am, zf), определено состояние перехода as или выходной символ wg. В противном случае КА называется полностью определенным.   am , z f   A  am  A, z f  Z ,    am , z f   W Например УУ МТ большинства из вас в ЛР1 представляет собой частично определенный автомат Мили. Задачи ТА Итак мы с вами кратко познакромильсь с объектом исследования ТА. В чем же заключается собственно исследование.То есть какие задачи для этих объектов наиболее часто требуется решить? Все объекты теории автоматов занимаются обработкой входных слов, поэтому многие задачи связаны с формальными языками (в частности ЯП). Прежде чем говорить о задачах, формализуем некоторые понятия. Символ — любой атомарный блок данных, который может производить эффект на машину. Чаще всего символ — это буква обычного языка, но может быть, к примеру, графическим элементом диаграммы. 12 Слово —цепочка (строка) символов. Алфавит — конечный набор различных символов (множество символов) Язык — множество слов, формируемых символами данного алфавита. Приведем примеры задач, решаемых в ТА 1) Провека на пустоту Принимает ли автомат какое-либо входное слово? 2) Распознаваемый язык Какой класс формальных языков распознается автоматами определенного типа? 3) Детерминизация Можно ли преобразовать данный недетерминированный автомат в детерминированный автомат, не меняя распознаваемый язык? (не уверена, чт это нужно упоминать) Недетерминированным называется объект ТА, который под воздействием входного символа может перейти одновременно в несколько состояний (все рассмотренные нами ранее объеекта были детерминированными). Так, например, существует понятие недетерминорованной МТ, недетрминированного КА. Для реализации таких объектов на прктике на кадом шаге создается необходимое число копий машины. 4) Синтез Построение автомата, распознающего заданный язык. 5) Минимизация Построение наименьшего автомата, распознающего заданный формальный язык. Вот такие задачи для этих объектов наиболее часто требуется решить разработчику. Конечно для большинства из них уже придуманы методы для их решения и наша задача в течении курса ТА будет – познакомиться с ними для того, чтобы в случае необходимости мы смоглы легко воспользоваться этим инструементом. С пактической точки зрения наибольший интерес представляют 2 последние задачи. Ими мы и будем заниматься. И начнем с последней. Понятие экивалентых и минимальных автоматов При выполнении ЛР1 многие из вас заметили, что для решения поставленной задачи можно построить МТ с разым числом состояний. Получается, что можно построить несколько машин (конечных автоматов), которые по внутренней структуре будут разными, а работать будут одинаково. Такие автоматы называются эквивалентыми. Два автомата называются эквивалентными, если их реакции на любое допустимое входное слово совпадают. Для КА Мили и Мура реакцией на входное слово будет выходное слово, выдаваемое автоматом. Построение по заданному АА эквивалентного АА, имеющего наименьшее возможное число состояний, называется минимизацией АА. За счет чего можно произвести минимизацию? 1) за счет удаления недостижимых состояний (состояний, в которые ни при каких входных словах мы не попадем) – это не такая интересная проблема 2) за счет удаления неразличимых (эквивалентных) состояний (состояний, в которых автомат на любую входную последовательность реагирует одинаково) Например, в нашем автомате Мура состояния а0 и а2 эквивалентны. Почему? Строго условие эквивалентности будет звучать так. Два состояния ai и aj являются эквивалентными, если для каждого символа zk из множества входных символов автомата справедливы утверждения: 1) при подаче входного символа zk автомат в состоянии ai выдает тот же символ, что и при подаче zk в состоянии aj; 13 2) из ai при подаче входного символа zk автомат переходит в состояние, эквивалентное состоянию, в которое переходит автомат под действием zk из aj. Красиво математически это можно записать так:   ai , z     a j , z  , z  Z ,  ai a j     ai , z    a j , z  , z  Z . 14 Лекция 3. Минимизация полностью определенных автоматов 1. Идея минимизации 2. Поиск недостижимых состояний. Пример конечного классического автомата. 3. Алгоритм Мура разбиения на эквивалентные состояния 4. Пример для автомата Мура 5. Пример для автомата Мили Про Димину минимизацию в программировании. Итак, в прошлый раз отметили, что для минимизации нужно 1) удалить недостижимые состояния 2) эквивалентные друг другу состояния заменить одним Алгоритм поиска недостижимых состояний. Недостижимыми называются такие состояния КА, которые не могут быть достигнуты из начального состояния воздействием любых входных символов. Идея поиска недостижимых состояний состоит в составлении множества всех достижимых состояний и сравнении полученного множества с множеством состояний. Достижимые состояния ищутся методом перебора по следующему алгоритму. Шаг 0: инициировать множество достижимых состояний начальным состоянием; R0 = {a0} Шаг 1: дополнить это множество состояниями, в которые переходит автомат из состояний, уже присутствующих в множестве при воздействии любых входных символов; R  R0  {a  A a    ar , z  , ar  R0 , z  Z } Шаг 2: если на шаге 1 множество не пополняется новыми элементами, то получен список достижимых состояний; остальные состояния КА недостижимы. Если R \ R0  0, то R0  R, перейти к шагу 1 Иначе N  A \ R Рассмотрим пример классического конечного автомата (жирные – финальные) a0 a1 a2 a3 a4 a5 a6 a a1 a3 a1 a3 a4 b a2 a4 a4 a6 a5 Вроде во все состояния есть переходы (кроме a0), однако проверим... проверяем по алгоритму, рисуем граф Поиск эквивалентных состояний О том, что такое эквивалентные состояния, мы говорили в прошлый раз. Напомню, что два состояния называются эквивалентны, если для них равны значения функции выходов и эквивалентны значения функции переходов:   ai , z     a j , z  , z  Z ,  ai a j     ai , z    a j , z  , z  Z . Для классчического конечного автомата, для автомата Мура и для автомата Мили (то. чт онаписано)… В любом случае есть 2 проблемы: 1) в этом определении присутствует рекурсия, причем для большого количества состояний она может быть глубокая, за ней трудно уследить 15 2) определение для двух состояний, а эквивалентными могут быть сразу 3 и больше, что тоже нелегко заметить Поэтому возникает нетривиальная задача разделения состояний на пересекающиеся группы эквивалентности. Для ее релшения существуют различные алгоритмы. Познакомимся с одним из алгоритмов минимизации полностью определенных автоматов, предложенным Эдвардом Муром в 1956 году Минимизация полностью определенных автоматов методом расщепления классов эквивалентных состояний (метод Мура) Алгоритм состоит из трех шагов: Шаг 0. Разбиение по выходным сигналам Состояния разбиваются на группы, так, чтобы для состояний в одной группе совпадали функции выходов. r  0, Gr  {g1r ,...g kr }, g1r  ...  g kr  A   ai     a j  ; ai , a j  g , g  Gr . (для автомата Мура) нуль-эквивалентные состояния (т.к. эквивалентны до подачи первого входного симола)   ai , z     a j , z  ; ai , a j  g , z  Z , g  Gr . (для автомата Мили) одноэквивалентные состояния (т.к. эквивалентны в момент первого входного симола) Для классического конечного автомата этот шаг пропускается. Это разбиение G0. Шаг 1. Разбиение по состоянимя перехода. Каждую группу из Gr-1 разбиваем так, чтобы для состояний в одной группе совпадали группы состояний переходов в разбиении Gr-1. r  r  1, ai  g r    ai , z   g r 1  g r  Gr ,    , g r 1  Gr 1 , z  Z .  a , z  g a j  g r    j r 1    Шаг 2. Проверка изменений Если разбиение совпало с предыдущим – получено финальное разбиение. Классы являются финальными. Если Gr=Gr-1 – конец. Иначе – перейти к шагу 1. Рассмотрим применение этого алгоритма для минимизации автомата Мура. z1 z2 a0 a4 a2 1 a1 a1 a0 2 a2 a0 a8 2 a3 a5 a4 1 a4 a4 a5 a5 a8 a3 a6 a3 a7 1 a7 a7 a6 1 a8 a1 a5 Рассмотрим применение этого алгоритма для минимизации автомата Мили z1 z2 a0 a5/1 a1/2 a1 a6/2 a0/1 a2 a3/1 a2/2 a3 a5/1 a0/1 a4 a6/2 a5/1 a5 a0/1 a4/2 a6 a7/1 a0/1 a7 a3/1 a7/2 16 Лекция 4. Минимизация полностью определенных автоматов методом треугольной таблицы 1. 2. 3. 4. Алгоритм минимизации Пример для автомата Мили Пример для автомата Мура Построение автоматной ленты Продолжаем тему минимизации. В прошлый раз познакомились с одним из алгоритмов объединения неразличимых состояний – алгоритмом Мура. Существуют другие алгоритмы. Будем тренироваться на нашем автомате Мили из прошлой лекции (на левой доске в столбик) a0 a1 a2 a3 a4 a5 a6 a7 z1 a5/1 a6/2 a3/1 a5/1 a6/2 a0/1 a7/1 a3/1 z2 a1/2 a0/1 a2/2 a0/1 a5/1 a4/2 a0/1 a7/2 Напомню, что два состояния называются эквивалентны, если для них равны значения функции выходов и эквивалентны значения функции переходов (справа на средней доске):   ai , z     a j , z  , z  Z ,  ai a j     ai , z    a j , z  , z  Z . Алгоритм треугольной таблицы (слева) Этот алгоритм основан на построении присутствующих в этом определении деревьев рекурсии. Например, два состояния 0 и 2 будут эквивалентны, если эквивалентны состояния 5 и 3 и 1 и 2 (начинаем рисовать дерево на средней доске) В итоге мы можем получить 2 варианта: 1) наткнемся на неэквивалентную пару (как в этой цепочке) – в этом случае все корневая пара и все пары на пути к неэквивалентному листу будут не эквивалентны 2) получим замкнутое дерево (как для 0 и 5) – в этом случае все пары в дереве будут эквиваленты Таким образом, для каждой пары состояний автомата можно определить ее эквивалентность. Визуально эквивалентность пар удобно представлять в виде треугольной таблицы (рисуем на средней доске). Здесь каждой паре соответствует одна клетка. Алгоритм разбиения на группы эквивалентных состояний с помощью треугольной таблицы состоит в следующем. (на левой доске) Шаг 1. Построить треугольную таблицу с заголовками строк a1, …, an и столбцов a0, …., an-1 Шаг 2. В каждой клетке (ai, aj) если z  Z :   ai , z     a j , z  (выходные сигналы не совпадают) записать x 17   иначе записать пары   ai , z  ,   a j , z  , z  Z (условие эквивалентности) (заполняем) Шаг 3. Для каждого условия, полученного на шаге 2, построить дерево эквивалентности Если дерево замкнуто, отметить клетки, соответствующие его вершинам, знаком V, иначе – отметить все клетки на пути к неэквивалентной паре знаком x (выполняем) Шаг 4. На основе полученных пар эквивалентных состояний составить группы эквивалентности (все состояния в группе должны быть попарно эквивалентны) (составляем) Получили те же группы. Теперь можно составить минимальный автомат. заменив каждую группу исходным состоянием. z1 z2 Потренируемся на автомате Мура. 1 2 2 a0 a1 a2 a3 a4 a1 a0 a5 a2 a0 a8 a4 1 a4 a4 a5 a5 a8 a3 a6 a3 a7 1 a7 a7 a6 1 a8 a1 a5 Мы получили автомат, эквивалентный заданному, в котором удалены эквивалентные состояния. Как доказать их эквивалентность? Эквивалентные ми называются автоматы, которые на любое входное слово реагируют одинаково. Неужели нужно перебрать все возможные входные слова, ведь их бесконечно много, так как они могут иметь бесконечную длину. Так же, как и при составлении алгоритма поиска недостижимых состояний, здесь нужно учесть, что при подаче входного слова в какой-то момент мы перестанем получать новую информацию, так как вернемся в состояние, в котором автомат уже был. Таким образом, для доказательства эквивалентности нужно просто придумать слово, которое использует все переходы исходного автомата. Если реакция минимизированного автомата на это слово будет идентичная – автоматы эквивалентны. Построим такое слово… Такая запись называется автоматной лентой. Если бы оказалось, что мы не могли побывать в какой-либо клеточке таблицы, это означало бы недостижимость соответствующего состояния. Теперь посмотрим, что будет, если подать это слово на второй автомат. Слова совпали, следовательно, автоматы эквивалентны. 18 Лекция 5. Минимизация частично определенных автоматов 1. Минимизация автомата Мили 2. Минимизация автомата Мура 3. Минимизация классических конечных автоматов Продолжаем тему минимизации. До сих пор говорили о полностью определенных автоматах. Сегодня – о частично определенных. Напоминаю, что частично определенный - автомат, для которого не все значения функции переходов и выходов определены (есть прочерки в таблице). Автомат Мили Например, автомат Мили a0 a1 a2 a3 a4 а5 0 a0/0 a1/0 a2/0 а3/1 1 a3/1 a3/1 a4/1 а0/0 a a3/0 a5/1 1) Так же, как и для полностью определенных автоматов минимизацию хорошо начинать с проверки достижимости всех состояний. Проверим наш автомат на недостижимые состояния. Шаг 0: инициировать множество достижимых состояний начальным состоянием; R0 = {a0} Шаг 1: дополнить это множество состояниями, в которые переходит автомат из состояний, уже присутствующих в множестве при воздействии любых входных символов; R  R0  {a  A a    ar , z  , ar  R0 , z  Z } Шаг 2: если на шаге 1 множество не пополняется новыми элементами, то получен список достижимых состояний; остальные состояния КА недостижимы. Если R \ R0  0, то R0  R, перейти к шагу 1 Иначе N  A \ R … a1 – недостижимое 2) Далее нужно объединить эквивалентные состояния. Особенность минимизации частично определенных автоматов в том, что минимальных автоматов, эквивалентных заданному, может построено несколько. Состояния полностью определенных автоматов разбиваются на группы эквивалентность единственным образом. А здесь из-за неопределенности могут появляться варианты. Например, состояние a2 можно приписать как к a0, так и к a3. И здесь наша задача выбрать такое распределение, которое приведет нас к минимальному числу состояний. Помощником в этом снова может быть треугольная таблица 2 v 3 0,2 v v 1,4 4 v x v 5 x v x v 2 3 4 Напоминаю, что каждая клеточка здесь соответствует паре состояний, и мы будем записывать в нее данные о эквивалентности. В отличие от полностью определенных автоматов здесь уже на первом этапе заполнения могут появиться галочки, если состояния не имеют общих входных символов. … 19 Заполнение треугольной таблицы завершено. В ней галочками отмечены пары эквивалентных состояний, а галочками с цифрами – пары условно эквивалентных. То есть эта пара эквивалента при объединении в одну группу указанных в условии пар. Выпишем пары и условия. Посмотрим, какие могут быть варианты разбиений. Построим минимальный автомат. Автомат Мура А сейчас обратимся к автомату Мура. 0 0 1 1 0 0 a0 a1 a2 a3 a4 а5 0 a2 a3 a2 а4 1 a1 a0 a4 а0 a a3 a5 Проверим недостижимость. Для него все то же самое… 1 2,3 v 1,0 2 x 3 x 4 v 5 2,4 x 0,1 x x v v x x 3,4 x x x v 1 2 3 4 Выпишем пары и условия. Посмотрим, какие могут быть варианты разбиений. Построим минимальный автомат. Минимизация классических конечных автоматов То, чего нет в ЛР, но что будет в КР не лекции. Например, конечный автомат a0 a1 a2 a3 a4 а5 a a4 a3 a2 а1 b a1 a3 a1 a0 a4 Напоминаю, что у классического конечного автомата не выходных сигналов, но есть множество финальных состояний (как у МТ). Если автомат завершает обработку входного слова в финальном состоянии, это слово допустимое, иначе – слово недопустимо. В отличие от МТ у конечного классического автомата могут быть переходы из финальных состояний. В кружочках – финальные состояния. Так же, как и для автоматов с выходами для классических конечных автоматов минимизация содержит 2 этапа 1) удаление недостижимых состояний 2) объединение эквивалентных состояний Недостижимость определятся так же, как для Мура и Мили. Недостижимо состояние a5. А с эквивалентностью чуть по-другому, но очень походе на автомат Мура. Здесь нет функции выходов, но есть финальные состояния. И вместо равенства функции выходов у 20 эквивалентных состояний мы должны требовать, чтобы они оба имели одинаковое отношение к финальности (или оба финальные или оба – нет).  0 {ai , a j }  F   ai a j   {ai , a j }    ai , z    a j , z  , z  Z . Это означает, что мы можем отметить финальные состояния одним выходным сигналом, а нефинальные – другим и минимизировать его как автомат Мура. 1 2 3 4 1,3 v x x 1,0 v 3,0 v x x x 2,3 x x 1,4 1 2 3 Строим минимальный автомат. В следующий раз поговорим о синтезе автоматов. 21