Раздел 5. Лекция 13. Абстрактный синтез конечных автоматов

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

Представление событий в автоматах

В основе рассматриваемого способа задания автоматов, лежит понятие событий, представимых в автоматах.

Пусть Y{y₁, y₂, …, y_k} – выходной алфавит конечного автомата S с фиксированным начальным состоянием a₀. Тогда каждой букве y_j, выходного алфавита можно поставить в соответствие множество входных слов S_j(x₁, x₂,…, x_m), которые вызывают появление на выходе автомата буквы y_j. Определенное таким образом множество слов S_j(x₁, x₂, …, x_m) называют событием, представленным в автомате выходным сигналом y_j.

Поэтому для задания конечного автомата, имеющего выходной алфавит Y{y₁, y₂, …, y_k}, достаточно разбить множество всех возможных входных слов на K событий S₁, S₂, …, S_k, представленных в автомате выходными сигналами y₁, y₂, …, y_k соответственно. Для частичного автомата необходимо, кроме того, задать множество S_з запрещенных слов. Таким образом, конечный автомат может быть задан таблицей, устанавливающей соответствия между событиями и буквами выходного алфавита. Зная набор событий S_j, можно, не пользуясь таблицами переходов и выходов, найти реакцию автомата на любое входное слово, для чего достаточно определить множество каких слов входного алфавита оно входит (то есть какому событию принадлежит).

Для описания автоматов на языке регулярных событий вводят ряд операций над событиями, то есть строят алгебру событий. Мы рассмотрим алгебру событий, введенную Клини и усовершенствованную академиком Глушковым В. М.

Соответствие событий буквам выходного алфавита

Операции в алгебре событий. Алгебра событий включает три операции: дизъюнкцию (объединение) событий, произведение событий и итерацию событий.

Дизъюнкцией событий называют событие S = S₁v S₂v…vS_k, состоящее из всех слов, входящих в события S₁, S₂, …, S_k.

Пример: Событие S₁ содержит слова x₁, x₂x₁, x₁x₁, т.е. S₁ = (x₁, x₂x₁, x₁x₁), а S₂=(x₂,x₁x₂). Тогда S = S₁ v S₂ = (x₁, x₂, x₁x₁, x₁x₂x₂x₁).

Произведением событий называется событие S = S₁* S₂* …,* S_k, состоящее из всех слов, полученных приписыванием к каждому слову события S1 каждого слова события S₂, затем слова события S₃ и т.д.

Пример: S₁ и S₂ те же. Тогда S = S₁* S₂ = (x₁x₂, x₁x₁x₂, x₂x₁x₂, x₂x₁x₁x₂, x₁x₁x₂, x₁x₁x₁x₂). Произведение событий не коммутативно, то есть слова, входящие в события S₁*S₂ и S₂*S₁ различны: то есть S₁*S₂ S₂*S₁. Поскольку произведение не коммутативно, следует различать операции «умножение справа» и «умножение слева». Например, относительно произведения событий S₁*S₂ можно сказать, что событие S₂ умножено на событие S₁ справа, а событие S₁ на S₂ – слева.

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

Итерацией события S называется событие{S}, состоящее из пустого слова e и всех слов вида S, SS, SSS и т.д. до бесконечности. То есть: {S} = e v S v SS v SSS v …

Пример: S=(x₂,x₁x₂), {S} = (e, x₂, x₂ x₂, x₂x₂x₂, …, x₁x₂, x₁x₂x₁x₂, …, x₂x₁x₂, x₁x₂x₂, …)

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

Теорема: Любые регулярные выражения и только они представимы в конечных автоматах.

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

Рассмотрим, как можно совершить переход от описательной формы задания алгоритмов работы конечных автоматов к представлению этих алгоритмов в виде регулярных выражений. С целью упрощения такого перехода вводят основные события, из которых с помощью операций дизъюнкции, умножения и итерации можно составить более сложные события, соответствующие заданному алгоритму работы автомата. За основные события принимают такие события, которые более часто встречаются в инженерной практике при синтезе схем ЭВМ. Пусть дан конечный алфавит X = (x₁, x₂, …, x_m).

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

Система основных событий

В эту систему мы включим те из наиболее часто встречающихся событий, которые используются при записи регулярных выражений на практических занятиях и курсовой работе. Пусть дан алфавит X{ x₁, x₂, …, x_m }.

1. Событие, состоящее из всех слов входного алфавита (всеобщее событие). F = {x₁ v x₂ v …v x_m}

2. Событие, содержащее все слова, оканчивающиеся буквой x_i. S = { x₁ v x₂ v …v x_i v …v x_m } xi = Fx_i

3. Событие, содержащее все слова, оканчивающиеся отрезком слова l₁ S = F l₁

4. Событие, содержащее все слова, начинающиеся с отрезка слова l₁ и оканчивающиеся на l₂: S = l₁ F l₂

5. Событие, содержащее только однобуквенные слова входного алфавита S = x₁ v x₂ v …v x_m

6. Событие, содержащее только двухбуквенные слова входного алфавита S = (x₁ v x₂ v …v x_m)( x₁ v x₂ v …v x_m)

7. Событие, содержащее все слова длиной r S = ( x₁ v x₂ v…v x_m)( x₁ v x₂ v…v x_m)…(x₁ v x₂ v…v x_m) - r членов

8. Событие, содержащее все слова, длина которых кратна r S = {( x₁ v x₂ v…v x_m)( x₁ v x₂ v…v x_m)…(x₁ v x₂ v…v x_m)} - r членов

9. Событие, состоящее из всех слов алфавита X{ x₁, x₂}, не содержащих комбинации букв x₁x₁ и оканчивающихся буквой x₂ S = { x₂ v x₁ x₂}

10. Событие, состоящее из всех слов алфавита X{ x₁, x₂}, не содержащих серии из r букв x₁ и оканчивающихся буквой x₂ S = { x₂ v x₁ x₂ v x₁x₁ x₂ v … v x₁x₁… x₁ x₂} - (r-1) членов.

Рассмотрим пример составления регулярного выражения.

Пример. Записать в виде регулярного выражения алгоритм работы автомата, сравнивающего два двоичных числа, представленных в последовательном коде. Количество разрядов числа – произвольно. Окончание чисел фиксируется подачей на вход автомата сигнала x_s. Если число, поданное на первый вход автомата, меньше числа, поданного на второй вход, то КА выдает сигнал y₁, если больше – то y₂, если оба числа равны – то y₃. Числа подаются на входы автомата младшими разрядами вперед. На входы автомата сравнения одновременно может поступить одна из четырех комбинаций сигналов 00,01,10,11, которые закодируем следующим образом x₀₀=00, x₀₁=01, x₁₀=10, x₁₁=11. При этом будем считать, что первая цифра каждой комбинации относится к первому входу, а вторая – ко второму входу. Таким образом, входной алфавит автомата включает пять букв X{ x₀₀, x₀₁, x₁₀, x₁₁, x_s }, а выходной три буквы Y{y₁, y₂, y₃}.

Два двоичных числа равны, если равны цифры в любых одинаковых разрядах. Поэтому событие, заключающееся в поступлении на вход автомата равных чисел, состоит из всех возможных слов, содержащих буквы x₀₀ и x₁₁. То есть S₃ = { x₀₀ v x₁₁} x_s.

События, представленные в автомате сигналами y₁ и y₂ можно записать в виде: S₁={x₀₀vx₀₁vx₁₀vx₁₁}x₀₁{x₀₀vx₁₁}x_s S₂={x₀₀vx₀₁vx₁₀vx₁₁}xx₁₀{x₀₀vx₁₁}x_s.

События S₁, S₂ и S₃ не охватывают всего множества слов, которые могут быть записаны в алфавите X{ x₀₀, x₀₁, x₁₀, x₁₁, x_s}, т.к. в эти события входят только слова, оканчивающиеся буквой x_s. Слова, не входящие в S₁, S₂ и S₃, должны быть представлены в автомате пустой буквой e: S₄ = S₁ v S₂ v S₃

Очевидно, что записанные выражения можно упростить, если входные сигналы 00 и 11 закодировать одной буквой, например x_r. Такое кодирование возможно, т.к. КА одинаково реагирует на эти комбинации. S₁={x_rvx₀₁vx₁₀}x₀₁{x_r}x_s S₂={x_rvx₀₁vx₁₀}x₁₀{x_r}x_s S₃={x_r}xs, S₄=S₁vS₂vS₃

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

1. S₁ v S₂ = S₂ v S₁ - закон коммутативности

2. (S₁vS₂)vS₃=S₁v(S₂vS₃)=S₁vS₂vS₃ - законы ассоциативности

3. S₁*(S₂*S₃) = (S₁*S₂)*S₃ - законы ассоциативности

4. S₁(S₂v S₃) = S₁S₂ v S₁S₃ - закон дистрибутивности

5. {{S}} = {S}

6. {S}*{S} = {S}

7. {{S₁} v {S₂} = { S₁ v S₂}

8. {e} = e

9. eS = Se = S

Методы абстрактного синтеза

Задача абстрактного синтеза заключается в составлении таблиц переходов и выходов автоматов по заданным условиям его функционирования, представленным в форме регулярных выражений. Абстрактный синтез обычно выполняется в два этапа:

1. Первый этап заключается в получении таблиц переходов и выходов в некоторой исходной форме. Построенный по этим таблицам автомат обычно содержит «лишние» внутренние состояния.

2. На втором этапе производится минимизация количества внутренних состояний заданного автомата.

Синтезируемый автомат может быть задан либо как автомат Мура, либо как автомат Мили. Поскольку для автомата Мура всегда можно построить эквивалентный автомат Мили, то достаточно рассмотреть алгоритм синтеза автомата Мура, который проще автомата Мили.

Алгоритм синтеза автомата Мура

Рассмотрим пример абстрактного синтеза автомата для случая, когда регулярные отношения составлены без применения операции итерации. Составим отмеченную таблицу переходов автомата, имеющего входной алфавит X{x₁, x₂} и реализующий следующий алгоритм.

При синтезе условимся начальное состояние автомата обозначать цифрой 0, а остальные состояния – десятичными числами 1, 2, 3 и т.д. Очевидно, самый простой, хотя и не экономный по числу используемых внутренних состояний автомата. Алгоритм синтеза заключается в следующем. Фиксируется начальное состояние и для входного слова, содержащего r букв, назначается r внутренних состояний. Переходы в автомате определяются так, что первая буква входного слова переводит автомат из начального состояния 0 в состояние 1, вторая буква из 1 в 2 и т.д. Аналогичные последовательности внутренних состояний назначаются для всех остальных слов. Затем все конечные состояния, в которые автомат попадает после подачи слов, входящих в событие S_i, отмечаются выходными сигналами y_i.

Чтобы система переходов автомата была определенной, для всех слов, имеющих одинаковые начальные отрезки, следует назначать одну и ту же последовательность состояний. Например, для регулярного события S₁ первая буква x₁ переводит автомат из начального состояния 0 в состояние 1, вторая буква x₂ – из 1 в 2.

Поскольку первая буква второго слова x₁x₁x₁, входящего в S₁ также есть x₁, то она переводит автомат из начального состояния 0 в 1. Вторая буква x₁ переводит автомат из 1 в 3, третья – из 3 в 4.

Первые две буквы слова x₁x₂x₂, входящего в S₂, совпадают с первым словом события S₁. Поэтому первые две буквы этого слова должны последовательно переводить автомат из 0 в 1, и из 1 в 2. Дальнейшие состояния обозначим числами 5, 6 и 7. Получившаяся в результате форма записи определяет разметку мест регулярных выражений.

Местами регулярного выражения называют промежутки между двумя буквами, между буквой и знаком дизъюнкции, а так же между буквой и скобкой. Кроме того, вводят начальное место, обозначаемое цифрой 0 и конечные места, отождествляемые с концом каждого слова. Для запрещенного события S_запр последовательность событий можно не назначать. Для размеченных регулярных выражений составляется отмеченная таблица переходов.

 Чтобы система переходов автомата была определена при подаче любого входного слова, кроме состояний 0 - 7, вводится еще одно состояние, которое обозначается звездочкой *. В это состояние автомат переходит при подаче входных слов, которые не входят в события S₁ и S₂. Выходным сигналом y₁ отмечены состояния 2 и 4, y₂ – состояния 5 и 7. Остальные состояния отмечены пустой буквой e.

Алгоритм синтеза усложняется, если регулярные выражения содержат итерационные скобки. При разметке регулярных выражений различают основные и пред основные места. Очевидно, некоторые места могут быть одновременно основными и предосновными.

Все основные места отмечаются различными десятичными числами, при этом всем начальным местам приписывается индекс 0. Затем каждое предосновные место отмечается совокупностью индексов основных мест. В эту совокупность входят индексы внутренних состояний, находясь в которых автомат может принять букву, стоящую справа от предосновного места.

Разметка регулярных выражений

Разметка регулярных выражений проводится по правилам подчинения мест. Общие правила подчинения мест регулярного выражения

1. Индекс места перед любыми скобками распространяется на начальные места всех дизъюнктивных членов, записанных в этих скобках.

2. Индекс конечного места, любого дизъюнктивного члена, заключенного в любые скобки, распространяется на место, непосредственно следующее за этими скобками.

3. Индекс места перед итерационными скобками распространяется на место, непосредственно следующее за этими скобками.

4. Индекс конечного места любого дизъюнктивного члена, заключенного в итерационные скобки, распространяется на начальные места всех дизъюнктивных членов, заключенных в эти итерационные скобки.

5. Индексы мест, слева и справа от которых стоят буквы, никуда не распространяются.

6. В автоматах многократного действия индекс конечного места всего выражения распространяется на те же места, на которые распространяется индекс начального места. Это правило справедливо только в тех случаях, когда событие представлено регулярным выражением так, что оно не содержит многократно повторяющихся слов, входящих в заданное событие. И тогда организация автомата многократного действия осуществляется путем разметки.

Смысл приведенных правил подчинения мест сводится к следующему: основному месту с индексом i подчиняется место j, если автомат, находящийся в состоянии i, может принять букву входного алфавита, записанную непосредственно справа от места j. Рассмотрим эти правила на примере синтеза автомата, описываемого следующим