Анализ и синтез конечных автоматов
Анализ – это осуществление некоторых испытаний (фактических или виртуальных) некоторого объекта с целью выяснения интересующих нас свойств.
Синтез – это «конструирование» сложного объекта из простых объектов. При этом мы задаем некоторые желаемые свойства синтезируемого объекта.
Анализ конечного автомата сводится к следующему: задан конечный автомат (таблицей или графом), дано начальное состояние автомата, дана последовательность входных сигналов. Найти последовательность выходных сигналов и соответствующих состояний конечного автомата.
Например, выбрав в имеющемся графе любое исходное состояние и последовательность 5-7 входных сигналов, построить соответствующее число пар выходных сигналов – состояний.
При синтезе комбинационных схем можно составить таблицу зависимости значения выходного сигнала от комбинации входных. Такая таблица однозначно определяет систему ПФ, описывающую работу КС.
Составить аналогичную таблицу, описывающую работу конечного автомата, не представляется возможным, т.к. множество допустимых входных слов автомата, вообще говоря, бесконечно. Поэтому для задания КА и используются таблицы переходов и выходов, которые позволяют представить соответствие между бесконечными множествами входных и выходных слов конечными таблицами. В связи с этим, прежде чем приступить к синтезу схемы КА необходимо составить таблицу переходов и выходов, что не всегда является простым делом особенно в тех случаях, когда алгоритм работы автоматов задан в описательной форме. Для того, чтобы упростить и формализовать процедуру построения таблиц переходов и выходов необходимо ввести такую исходную форму задания автоматов, переход к которой от алгоритмов, сформулированных в описательной форме, не представляет трудностей. Мы рассмотрим один из возможных способов формального задания автоматов, а именно, задание автомата на языке регулярных событий.
Событием называют любое множество слов входного алфавита X {x1, x2, …,xm} автомата.
Пусть Y{y1, y2, …, yk} – выходной алфавит конечного автомата S с фиксированным начальным состоянием a0. Тогда каждой букве yj, выходного алфавита можно поставить в соответствие множество входных слов Sj(x1, x2,…, xm), которые вызывают появление на выходе автомата буквы yj. Определенное таким образом множество слов Sj(x1, x2, …, xm) называют событием, представленным в автомате выходным сигналом yj.
Поэтому для задания конечного автомата, имеющего выходной алфавит Y{y1, y2, …, yk}, достаточно разбить множество всех возможных входных слов на K событий S1, S2, …, Sk, представленных в автомате выходными сигналами y1, y2, …, yk соответственно. Для частичного автомата необходимо, кроме того, задать множество Sз запрещенных слов. Таким образом, конечный автомат может быть задан таблицей, устанавливающей соответствия между событиями и буквами выходного алфавита. Зная набор событий Sj, можно, не пользуясь таблицами переходов и выходов, найти реакцию автомата на любое входное слово, для чего достаточно определить в множество каких слов входного алфавита оно входит (т.е. какому событию принадлежит).
| Событие | буква выходного алфавита |
| S1(x1, x2,…, xm) S2(x1, x2,…, xm) … Sk(x1, x2,…, xm) Sx(x1, x2,…, xm) | y1 y2 … yk - |
Для описания автоматов на языке регулярных событий вводят ряд операций над событиями, т.е. строят алгебру событий. Мы рассмотрим алгебру событий, введенную Клини и усовершенствованную академиком Глушковым В. М.
Алгебра событий включает три операции:
· Дизъюнкцию (объединение) событий;
· Произведение событий;
· Итерацию событий.
Дизъюнкцией событий S1, S2, …, Sk называют событие S = S1vS2v…vSk, состоящее из всех слов, входящих в события S1, S2, …, Sk.
Пример. Событие S1 содержит слова x1, x2x1, x1x1, т.е. S1 = (x1, x2x1, x1x1), а S2 = (x2, x1x2). Тогда S = S1vS2 = (x1, x2, x1x1, x1x2, x2x1).
Произведением событий S1, S2, …, Sk называется событие S = S1* S2* …,*Sk, состоящее из всех слов, полученных приписыванием к каждому слову события S1 каждого слова события S2, затем слова события S3 и т.д.
Пример. S1 и S2 те же. S = S1*S2 = (x1x2, x1x1x2, x2x1x2, x2x1x1x2, x1x1x2, x1x1x1x2).
Произведение событий не коммутативно, т.е. слова, входящие в события S1S2 и S2S1 различны. Поскольку произведение не коммутативно, следует различать операции «умножение справа» и «умножение слева». Например, относительно произведения событий S1S2 можно сказать, что событие S2 умножено на событие S1справа, а событие S1на S2 слева.
Третьей операцией, применяемой в алгебре событий, является одноместная операция итерация, которая применима только к одному событию. Для обозначения итерации вводят фигурные скобки, которые называются итерационными.
Итерацией события S называется событие {S}, состоящее из пустого слова e и всех слов вида S, SS, SSS и т.д. до бесконечности. Т.е. {S} = e v S v SS v SSS v….
Пример. S = (x2, x1x2).
{S} = (e, x2, x2x2, x2x2x2, …, x1x2, x1x2x1x2, …, x2x1x2, x1x2x2, …)
При синтезе конечных автоматов важнейшую роль играют регулярные события. Пусть дан конечный алфавит X = (x1, x2, …, xm).
Определение. Любое событие, которое можно получить из букв данного алфавита с помощью конечного числа операции дизъюнкции, произведения и итерации, называется регулярным событием, а выражение, составленное с помощью этих операций – регулярным выражением.
Очевидно любое событие, состоящее из конечного множества слов, является регулярным. Действительно, такие события можно представить в виде дизъюнкции всех входящих в него слов, образованных из букв заданного алфавита с помощью операции умножения. События, состоящие из бесконечного числа слов, могут быть как регулярными, так и не регулярными.
Теорема. Любые регулярные выражения и только они представимы в конечных автоматах.
Из этой теоремы следует, что любой алгоритм преобразования информации, который можно записать в виде регулярного выражения, реализуется конечным автоматом. С другой стороны, любые конечные автоматы реализуют только те алгоритмы, которые могут быть записаны в виде регулярных выражений.
Рассмотрим, как можно совершить переход от описательной формы задания алгоритмов работы конечных автоматов к представлению этих алгоритмов в виде регулярных выражений. С целью упрощения такого перехода вводят основные события, из которых с помощью операций дизъюнкции, умножения и итерации можно составить более сложные события, соответствующие заданному алгоритму работы автомата. За основные события принимают такие события, которые более часто встречаются в инженерной практике при синтезе схем ЦВМ.
Задача абстрактного синтеза заключается в составлении таблиц переходов и выходов автоматов по заданным условиям его функционирования, представленным в форме регулярных выражений.
Абстрактный синтез обычно выполняется в два этапа:
1. Первый этап заключается в получении таблиц переходов и выходов в некоторой исходной форме. Построенный по этим таблицам автомат обычно содержит «лишние» внутренние состояния.
2. На втором этапе производится минимизация количества внутренних состояний заданного автомата.
Синтезируемый автомат может быть задан либо как автомат Мура, либо как автомат Мили. Поскольку для автомата Мура всегда можно построить эквивалентный автомат Мили, то достаточно рассмотреть алгоритм синтеза автомата Мура, который проще автомата Мили.
Рассмотрим пример абстрактного синтеза автомата для случая, когда регулярные отношения составлены без применения операции итерации. Составим отмеченную таблицу переходов автомата, имеющего входной алфавит X{x1, x2} и реализующий следующий алгоритм.
S1 = x1x2 v x1x1x1 | y1 Sзапр. =x1 v x2x2x2
___________
S2 = x1x2x2 v x2x2 | y2 S4 = S1 v S2 v S3| e.
При синтезе условимся начальное состояние автомата обозначать цифрой 0, а остальные состояния – десятичными числами 1, 2, 3 и т.д. Очевидно, самый простой, хотя и не экономный по числу используемых внутренних состояний автомата, алгоритм синтеза заключается в следующем. Фиксируется начальное состояние и для входного слова , содержащего r букв, назначается r внутренних состояний. Переходы в автомате определяются так, что первая буква входного слова переводит автомат из начального состояния 0 в состояние 1, вторая буква из 1 в 2 и т.д. Аналогичные последовательности внутренних состояний назначаются для всех остальных слов. Затем все конечные состояния, в которые автомат попадает после подачи слов, входящих в событие Si, отмечаются выходными сигналами yi.
Чтобы система переходов автомата была определенной, для всех слов, имеющих одинаковые начальные отрезки, следует назначать одну и ту же последовательность состояний. Например, для регулярного события S1 первая буква x1 переводит автомат из начального состояния 0 в состояние 1, вторая буква x2 – из 1 в 2.
S = | x1| x2 | v | x1| x1| x1|
0 1 2 0 1 3 4
S = | x1| x2 | x2 | v | x2| x2|
0 1 2 5 0 6 7
Поскольку первая буква второго слова x1x1x1, входящего в S1 также есть x1, то она переводит автомат из начального состояния 0 в 1. Вторая буква x1 переводит автомат из 1 в 3, третья – из 3 в 4.
Первые две слова x1x2x2, входящего в S2, совпадают с первым словом события S1. Поэтому первые две буквы этого слова должны последовательно переводить автомат из 0 в 1, и из 1 в 2. Дальнейшие состояния обозначим числами 5, 6 и 7. Получившаяся в результате форма записи определяет разметку мест регулярных выражений.
Местами регулярного выражения называют промежутки между двумя буквами, между буквой и знаком дизъюнкции, а так же между буквой и скобкой. Кроме того, вводят начальное место, обозначаемое цифрой 0 и конечные места, отождествляемые с концом каждого слова. Для запрещенного события Sзапр последовательность событий можно не назначать.
Для размеченных регулярных выражений составляется отмеченная таблица переходов.
| e | e | y1 | e | y1 | y2 | e | y2 | E | |
| xj\ai | * | ||||||||
| x1 | * | * | * | * | * | * | |||
| x2 | * | * | * | * | * |
Чтобы система переходов автомата была определена при подаче любого входного слова, кроме состояний 0 ё 7, вводится еще одно состояние, которое обозначается звездочкой *. В это состояние автомат переходит при подаче входных слов, которые не входят в события S1 и S2. Выходным сигналом y1 отмечены состояния 2 и 4, y2 – состояния 5 и 7. Остальные состояния отмечены пустой буквой e.
Алгоритм синтеза усложняется, если регулярные выражения содержат итерационные скобки.
При разметке регулярных выражений различают основные и предосновные места.
Все места регулярного выражения, слева от которых стоит буква, а так же все начальные места называют основными.
Все места, справа от которых стоит буква, называют предосновными. Очевидно, некоторые места могут быть одновременно основными и предосновными.
Все основные места отмечаются различными десятичными числами, при этом всем начальным местам приписывается индекс 0. Затем каждое предосновное место отмечается совокупностью индексов основных мест. В эту совокупность входят индексы внутренних состояний, находясь в которых автомат может принять букву, стоящую справа от предосновного места.
Разметка регулярных выражений проводится по правилам подчинения мест. Рассмотрим эти правила на примере синтеза автомата, описываемого следующим регулярным выражением:
S = | {| x2| v | x1| x2| v | x1| x1| x2|} | x1| x1| x1| {| x1| }| x2|
0 1 2 3 4 5 6 7 8 9 10 11
В этом автомате сигнал y1 выдается после поступления подряд 3-ех букв x1, а y2 – после x2, следующей за серией их трех и более букв x1. В остальных случаях выдается буква e.
Индексы основных мест записываются непосредственно под регулярными выражениями, а индексы предосновных мест располагаются ниже индексов основных мест, под горизонтальной чертой. Выражение имеет 12 основных мест (от 0 до 12).
Проведем разметку предосновных мест. В начале определим, какие буквы может принять автомат, если он находится в состоянии 0. Поскольку на вход автомата может поступить любое из трех слов, записанных в итерационных скобках, то индекс 0 распространяется на каждое из трех предосновных мест, расположенных в начале этих слов. Учитывая, что событие, соответствующее выражению, записанному в итерационных скобках, содержит пустое слово е, индекс 0 распространяется на предосновное место, расположенное сразу за скобками. Это означает, что в частном случае ни одно из трех слов, заключенных в итерационные скобки, на вход автомата не поступит и тогда первой буквой, которую принимает автомат, является буква x1, стоящая непосредственно за итерационными скобками. Таким образом все эти предосновные места подчинены месту с индексом 0.
Теперь найдем предосновные места, на которые распространяется индекс 1. Если автомат находится в состоянии 1, то он может принять букву x2, расположенную слева от места 1, т.к. эта буква находится в итерационных скобках и, следовательно, неоднократно может повторятся во входном слове автомата. Кроме того, в состоянии 1 автомат может принять начальные буквы других слов, расположенных в итерационных скобках, и букву x1, непосредственно следующую за этими скобками. Таким образом, месту с индексом 1 в данном случае подчиняются те же предосновные места, что и месту с индексом 0.Если автомат находится в состоянии 2, то он может принять только букву x2, расположенную справа от места с индексом 2. Поэтому индекс распространяется на единственное предосновное место, являющееся одновременно основным местом 2. Аналогично можно найти подчиненные места других основных мест.
По окончании слева, входящего в событие S автомат переходит в состояние 11, после чего на вход автомата может поступить второе слово, этого события S, т.к. мы считаем, что автомат многократного действия. Автоматами многократного действия называются такие автоматы, которые могут неоднократно принимать слова, входящие в события, представленные в автомате. В таких автоматах индекс конечного места распространяется на те же предосновные места, на которые распространяется индекс начального места, т.е. по окончании очередного слова, на вход автомата этого слова может поступить вновь.
Сформулируем теперь общие правила подчинения мест регулярного выражения.
1. Индекс места перед любыми скобками распространяется на начальные места всех дизъюнктивных членов, записанных в этих скобках.
2. Индекс конечного места, любого дизъюнктивного члена, заключенного в любые скобки, распространяется на место, непосредственно следующее за этими скобками.
3. Индекс места перед итерационными скобками распространяется на место, непосредственно следующее за этими скобками.
4. Индекс конечного места любого дизъюнктивного члена, заключенного в итерационные скобки, распространяется на начальные места всех дизъюнктивных членов, заключенных в эти итерационные скобки.
5. Индексы мест, слева и справа от которых стоят буквы, никуда не распространяются.
6. В автоматах многократного действия индекс конечного места всего выражения распространяется на те же места, на которые распространяется индекс начального места. Это правило справедливо только в тех случаях, когда событие представлено регулярным выражением так, что оно не содержит многократно повторяющихся слов, входящих в заданное событие. И тогда организация автомата многократного действия осуществляется путем разметки.
Смысл приведенных правил подчинения мест сводится к следующему: основному месту с индексом i подчиняется место j, если автомат, находящийся в состоянии i, может принять букву входного алфавита, записанную непосредственно справа от места j.
По размеченному регулярному выражению теперь можно составить таблицу переходов автомата. Однако перед построением таблицы целесообразно уменьшить число индексов основных мест, а следовательно и число внутренних состояний автомата.
На этом первом этапе минимизации внутренних состояний можно пользоваться следующим правилом:
Если несколько предосновных мест отмечено одинаковой совокупностью индексов и справа от этих мест записаны одинаковые буквы, можно отметить одинаковыми индексами.
В полученном нами выражении основные места 2, 4 и 7 можно отметить общим индексом, т.к. слева от каждого из этих мест записана буква x1, а предосновные места, предшествующие этой букве, имеют одинаковую совокупность индексов (0, 1, 3, 6, 11). Теперь с учетом этого проведем новую разметку.
= | {| x2| v | x1| x2| v | x1| x1| x2|} | x1| x1| x1| {| x1| }| x2|
0 1 2 3 2 4 5 2 6 7 8 9
0 0 2 0 2 4 0 2 6 7 7
1 1 1 1 8 8
3 3 3 3
5 5 5 5
9 9 9 9
На этом первый этап минимизации (минимизации по регулярному выражению) закончен.
Составим теперь отмеченную таблицу переходов автомата. Определим вначале внутренние состояния, в которые переходит автомат из состояния 0 при подаче на его вход сигнала x1. Для этого найдем все предосновные места, содержащие индекс 0, справа от которых записана буква x1. Таких мест в выражении три. Все основные места, расположенные за этой буквой x1, отмечены индексом 2. Следовательно, автомат из состояния 0 под действием сигнала x1 переходит в состояние 2. Аналогично, сигнал x2 переводит автомат из состояния 0 в состояние 1, т.к. за предосновным, содержащим индекс 0, после буквы x2 расположено основное место с индексом 1. Таким же образом определяются переходы автомата их других внутренних состояний. Сигнал y1 выдается после поступления подряд трех букв x1, т.е. в состоянии 6, а сигнал y2 – после x2, следующей за серией из трех и более букв, т.е. в состоянии 8. В остальных случаях выдается пустая буква е. Отсюда получаем следующую отмеченную таблицу переходов:
| yg | e | e | e | e | e | e | y1 | e | y2 |
| xj\ai | |||||||||
| x1 | |||||||||
| x2 |
| yg | E | e | e | y1 | e | y2 |
| xj\ai | A0 | a1 | a2 | a3 | a4 | a5 |
| x1 | A1 | a2 | a3 | a4 | a4 | a1 |
| x2 | A0 | a0 | a0 | a5 | a5 | a0 |
Из построенной таблицы видно, что из состояний 0, 1,3 и 5 автомат сигналами x1 и x2 переводится в одинаковые состояния (2 и 1). Кроме того, все перечисленные состояния отмечены одинаковыми выходными сигналами. Поэтому состояния 0, 1, 3 и 5 можно объединить в одно состояние, обозначив его как а0. Введем также обозначения: 2 – а1; 4 – а2; 6 – а3; 7 – а4; 8 – а5. Тогда получим упрощенную таблицу переходов автомата. В этой таблице из состояний а3 и а4 под действием входных сигналов х1 и х2 автомат переходит в одинаковые состояния а4 и а5. Но объединять эти состояния нельзя, т.к. отмечены разными выходными сигналами. По этой же причине нельзя объединять состояния а0 и а5. Объединение состояний и составляет второй этап минимизации, причем объединяются только такие состояния, которые отмечены одинаковыми выходными сигналами, и из которых под действием одинаковых входных сигналов происходит переход в одинаковые состояния. Очевидно, у таких состояний должны совпадать столбцы таблицы переходов.