|
|
Абстрактный синтез конечных автоматовСтр 1 из 4Следующая ⇒ Основные понятия и определения В вычислительной технике используются схемы двух классов: комбинационные схемы и цифровые автоматы. Отличительной особенностью КС является наличие функциональной зависимости между входными и выходным сигналами: y(t) = f(x(t)). Причем при отсутствии входных сигналов выходные сигналы также отсутствуют, поскольку такие схемы не имеют памяти. В отличии КС схемы второго класса содержат в своем составе элементы памяти (запоминающие элементы). Эти схемы называются цифровыми автоматами (ЦА) или просто автоматами. В ЦА выходные сигналы в данный момент времени зависят не только от значения входных сигналов в тот же момент времени, но и от состояния схемы, которое, в свою очередь, определяется значениями входных сигналов, поступивших в предшествующие моменты времени. Введем основные понятия и определения. Автомат – это дискретный преобразователь информации, способный принимать различные состояния, переходить под воздействием входных сигналов из одного состояния в другое и выдавать различные выходные сигналы. Если множество состояний автомата, а так же множества входных и выходных сигналов конечны, то автомат называется конечным автоматом. Кодирование информации Информацию, поступающую на вход автомата, а так же выходную информацию, принято кодировать конечной совокупностью символов. Эту совокупность называют алфавитом, отдельные символы, образующие алфавит – буквами, а любые упорядоченные последовательности букв – словами в этом алфавите. Например: в алфавите X = (x1, x2), состоящем из двух букв, словами будут: x1, x2, x1x1, x1x2, x2x1, x2x2, x1x1x1 и т.д. Наряду со словами, состоящими не менее чем из одной буквы, введем слово, не содержащее ни одной буквы, которое будем обозначать символом е и называть пустым словом или пустой буквой. Математической моделью реального КА является абстрактный автомат, который имеет один входной канал и один выходной канал (рис. 4.1):
Рис. 4.1. Абстрактный автомат Автомат функционирует в дискретные моменты времени, интервал между которыми Т называется тактом. При этом в каждый дискретный момент времени на вход автомата поступает одна буква входного алфавита, автомат переходит из одного состояния в другое и выдается одна буква выходного алфавита. В зависимости от того, как задается длительность такта Т, различают автоматы синхронного действия (T = const) и асинхронного действия (T≠ const). Мы будем рассматривать, в основном, синхронные автоматы, функционирующие в дискретные моменты времени, которые можно обозначить целыми неотрицательными натуральными числами t = 0, 1, 2, 3, …, имеющими смысл номера такта. Для задания любого КА S необходимо задавать совокупность из пяти объектов: S{A, X, Y, d, l}, где A = {a0, a1, a2,..., am,..., aM} – множество состояний автомата, X = {x1, x2, …, xf,…, xF} – множество входных сигналов или входной алфавит, Y = {y1, y2, …, yg,…, yG} – множество выходных сигналов или выходной алфавит, d – функция переходов, определяющая состояние автомата в момент времени (t + 1) в зависимости от состояния автомата и входного сигнала в момент времени t, т.е. a(t + 1) = d [a(t), x(t)], 1 – функция выходов, определяющая значение выходного сигнала в зависимости от состояния автомата и входного сигнала в тот же момент времени, т.е. y(t) = l[a(t), x(t)]. Если множества А, Х и У конечны, то автомат называется конечным. Автомат работает следующим образом. В каждый момент времени t он находится в определенном состоянии a(t) из множества А возможных состояний, причем в начальный момент времени t = 0 он находится в состоянии a0. Автомат воспринимает входной сигнал x(t), выдает выходной сигнал y(t) = l[a(t), x(t)] и переходит в состояние a(t + 1) = d[a(t), x(t)]. Другими словами, абстрактный автомат каждой паре символов a(t) и x(t) ставит в однозначное соответствие пару символов a(t + 1) и y(t). Такие автоматы называют детерминированными.
Способы задания автоматов Чтобы задать конечный автомат S, необходимо описать все элементы множества S = {A, X, Y, d, l}, т.е. необходимо описать входной и выходной алфавиты и алфавит состояний, а также функции переходов d и выходов l. При этом среди множества A = {a0, a1,... aM} необходимо выделить начальное состояния a0, в котором автомат находится в момент времени t = 0. Существует несколько способов задания работы автомата, но наиболее часто используются табличный и графический. Табличный способ При табличном способе задания автомат Мили описывается двумя таблицами: таблицей переходов и таблицей выходов: Таблица переходов
Таблица выходов
Строки этих таблиц соответствуют входным сигналам x(t), а столбцы – состояниям. На пересечении столбца ai и строки xj в таблице переходов ставится состояние as = d[ ai, xj], в которое автомат перейдет из состояния ai под воздействием сигнала xj, а в таблице выходов – соответствующий этому переходу выходной сигнал yg = l[ai, xj]. Иногда автомат Мили задают совмещенной таблицей переходов и выходов:
Так как в автомате Мура выходной сигнал однозначно определяется состоянием автомата, то для его задания требуется только одна таблица, которая называется отмеченной таблицей переходов автомата Мура:
В этой таблице каждому столбцу приписан, кроме состояния ai, еще и выходной сигнал y(t) = l(a(t)), соответствующий этому состоянию. Таблица переходов автомата Мура называется отмеченной потому, что каждое состояние отмечено выходным сигналом. Задание таблиц переходов и выходов полностью описывает работу конечного автомата, поскольку задаются не только сами функции переходов и выходов, но также и все три алфавита: входной, выходной и алфавит состояний. Рассмотрим примеры табличного задания автоматов Мили и Мура: Автомат Мура:
Автомат Мили:
По этим таблицам можно найти реакцию автомата на любое входное слово. Для автомата Мура: x1 x2 x2 x2 x1 … a0 a2 a4 a1a4 y2 y1 y2 y1y2
Для автомата Мили: x1 x2 x2 x2 x1 … a0 a1 a0 a0 a0 a1 y1 y1 y2 y2 y1 Графический способ При графическом способе задание автомата осуществляется с помощью графа. Этот способ основан на использовании ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги – переходам между ними. Две вершины графа ai и as соединяются дугой, направленной от ai к as, если в автомате имеется переход из ai в as, то есть as = d(ai, xj). В автомате Мили (рис. 4.2) дуга отмечается входным сигналом xj, под действием которого происходит этот переход, и выходным сигналом yg, который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние автомата. В автомате Мура (рис. 4.3) в вершинах графа кроме состояния автомата отмечается соответствующий выходной сигнал, а дуга отмечается только входным сигналом xj, под действием
Операции в алгебре событий Алгебра событий включает три операции: дизъюнкцию (объединение) событий, произведение событий и итерацию событий. Дизъюнкцией событий называют событие S = S 1 v S 2 v …v SG, состоящее из всех слов, входящих в события S 1, S 2, …, SG. Пример. Событие S 1 содержит слова x 1, x 1 x 1, x 2 x 1, т.е. S 1 = (x 1, x 1 x 1, x 2 x 1), а Произведением событий называется событие Пример. При тех же событиях S 1 и S 2, Третьей операцией, применяемой в алгебре событий, является одноместная операция итерация, которая применима только к одному событию. Для обозначения итерации вводят фигурные скобки, которые называются итерационными. Итерацией события S называется событие { S }, состоящее из пустого слова e и всех слов вида S, SS, SSS и т.д. до бесконечности, т.е.: Пример. S = (x 2, x 1 x 2). Тогда { S } = (e, x 2, x 2 x 2, x 2 x 2 x 2, …, x 1 x 2, x 1 x 2 x 1 x 2, …, x 2 x 1 x 2, x 1 x 2 x 2, …) При синтезе конечных автоматов важнейшую роль играют регулярные события. Любое событие, состоящее из конечного множества слов, является регулярным. Действительно, такие события можно представить в виде дизъюнкции всех входящих в него слов, образованных из букв заданного алфавита с помощью операции умножения. События, состоящие из бесконечного числа слов, могут быть как регулярными, так и не регулярными. Теорема: Любые регулярные выражения и только они представимы в конечных автоматах. Из этой теоремы следует, что любой алгоритм преобразования информации, который можно записать в виде регулярного выражения, реализуется конечным автоматом. С другой стороны, любые конечные автоматы реализуют только те алгоритмы, которые могут быть записаны в виде регулярных выражений. Рассмотрим, как можно совершить переход от описательной формы задания алгоритмов работы конечных автоматов к представлению этих алгоритмов в виде регулярных выражений. С целью упрощения такого перехода вводят основные события, из которых с помощью операций дизъюнкции, умножения и итерации можно составить более сложные события, соответствующие заданному алгоритму работы автомата. За основные события принимают такие события, которые более часто встречаются в инженерной практике при синтезе схем ЭВМ. Пусть дан конечный алфавит X = (x 1, x 2, …, xm). Регулярное событие – это любое событие, которое можно получить из букв данного алфавита с помощью конечного числа операций дизъюнкции, произведения и итерации. Регулярное выражение – любое выражение, составленное с помощью операций дизъюнкции, произведения и итерации. Система основных событий В эту систему мы включим те из наиболее часто встречающихся событий, которые используются при записи регулярных выражений на практических занятиях и курсовой работе. Пусть дан алфавит X { x 1, x 2, …, xm }. 1. Событие, состоящее из всех слов входного алфавита (всеобщее событие): 2. Событие, содержащее все слова, оканчивающиеся буквой xi: 3. Событие, содержащее все слова, оканчивающиеся отрезком слова l 1: 4. Событие, содержащее все слова, начинающиеся с отрезка слова l 1 и оканчивающиеся на l 2: S = l 1 F l 2. 5. Событие, содержащее только однобуквенные слова входного алфавита: 6. Событие, содержащее только двухбуквенные слова входного алфавита: 7. Событие, содержащее все слова длиной r: S = (x 1 v x 2 v…v xm)(x 1v x 2 v…v xm)…(x 1 v x 2 v…v xm) - r членов. 8. Событие, содержащее все слова, длина которых кратна r: S = {(x 1 v x 2 v…v xm)(x 1 v x 2 v…v xm)…(x 1 v x 2 v…v xm )} - r членов 9. Событие, состоящее из всех слов алфавита X { x 1, x 2}, не содержащих комбинации букв x 1 x 1 и оканчивающихся буквой x 2: S = { x 2 v x 1 x 2}. 10. Событие, состоящее из всех слов алфавита X { x 1, x 2}, не содержащих серии из r букв x 1 и оканчивающихся буквой x 2: S = { x 2 v x 1 x 2 v x 1 x 1 x 2 v … v x 1 x 1… x 1 x 2 } - (r – 1) членов. Рассмотрим пример составления регулярного выражения. Пример. Записать в виде регулярного выражения алгоритм работы автомата, сравнивающего два двоичных числа, представленных в последовательном коде. Количество разрядов числа – произвольно. Окончание чисел фиксируется подачей на вход автомата сигнала xs. Если число, поданное на первый вход автомата, меньше числа, поданного на второй вход, то КА выдает сигнал y 1, если больше – то y 2, если оба числа равны – то y 3. Числа подаются на входы автомата младшими разрядами вперед. На входы автомата сравнения одновременно может поступить одна из четырех комбинаций сигналов 00, 01, 10, 11, которые закодируем следующим образом x 00=00, x 01=01, x 10=10, x 11=11. При этом будем считать, что первая цифра каждой комбинации относится к первому входу, а вторая – ко второму входу. Таким образом, входной алфавит автомата включает пять букв X { x 00, x 01, x 10, x 11, xs }, а выходной – три буквы Y { y 1, y 2, y 3}:
Два двоичных числа равны, если равны цифры в любых одинаковых разрядах. Поэтому событие, заключающееся в поступлении на вход автомата равных чисел, состоит из всех возможных слов, содержащих буквы x 00 и x 11. То есть S 3 = { x 00 v x 11} xs. События, представленные в автомате сигналами y 1 и y 2, можно записать соответственно в виде: S 1 = { x 00v x 01v x 10v x 11} x 01{ x 00v x 11} xs, S 2 = { x 00v x 01v x 10v x 11} x 10{ x 00v x 11} xs. События S 1, S 2 и S 3 не охватывают всего множества слов, которые могут быть записаны в алфавите X { x 00, x 01, x 10, x 11, xs }, т.к. в эти события входят только слова, оканчивающиеся буквой xs. Слова, не входящие в S 1, S 2 и S 3, должны быть представлены в автомате пустой буквой e: Очевидно, что записанные выражения можно упростить, если входные сигналы 00 и 11 закодировать одной буквой, например xr. Такое кодирование возможно, т.к. КА одинаково реагирует на эти комбинации: S 3 = { xr } xs, S 1={ xr v x 01v x 10} x 01{ xr } xs, S 2 = { xr v x 01v x 10} x 10{ x 00v x 11} xs, Заметим, что одно и тоже регулярное событие может быть представлено различными регулярными выражениями. Поэтому встает задача отыскания таких регулярных выражений, которые позволяют представлять события наиболее простыми формулами. Рассмотрим несколько основных соотношений, которые используются при преобразовании регулярных выражений: 1. S 1 v S 2 = S 2 v S 1 – закон коммутативности; 2. (S 1v S 2) v S 3 = S 1 v (S 2 v S 3) = S 1 v S 2 v S 3 – законы ассоциативности; 3. 4. 5. {{ S }} = { S }; 6. 7. {{ S 1} v { S 2}} = { S 1 v S 2}; 8. { e } = e; 9. eS = Se = S. Методы абстрактного синтеза Задача абстрактного синтеза заключается в составлении таблиц переходов и выходов автоматов по заданным условиям его функционирования, представленным в форме регулярных выражений. Абстрактный синтез обычно выполняется в 2 этапа: 1. Первый этап заключается в получении таблиц переходов и выходов в некоторой исходной форме. Построенный по этим таблицам автомат обычно содержит «лишние» внутренние состояния. 2. На втором этапе производится минимизация количества внутренних состояний заданного автомата. Синтезируемый автомат может быть задан либо как автомат Мура, либо как автомат Мили. Поскольку для автомата Мура всегда можно построить эквивалентный автомат Мили, то достаточно рассмотреть алгоритм синтеза автомата Мура, который проще автомата Мили. Второй этап минимизации Составим отмеченную таблицу переходов автомата. Определим вначале внутренние состояния, в которые переходит автомат из состояния 0 при подаче на его вход сигнала x 1. Для этого найдем все предосновные места, содержащие индекс 0, справа от которых записана буква x 1. Таких мест в выражении 3. Все основные места, расположенные за этой буквой x 1, отмечены индексом 2. Следовательно, автомат из состояния 0 под действием сигнала x 1 переходит в состояние 2. Аналогично сигнал x 2 переводит автомат из состояния 0 в состояние 1, так как за предосновным местом, содержащим индекс 0, после буквы x 2расположено основное место с индексом 1. Таким же образом определяются переходы автомата их других внутренних состояний. Сигнал y 1 выдается после поступления подряд трех букв x 1, то есть в состоянии 6, а сигнал y 2 – после x 2, следующей за серией из трех и более букв, то есть в состоянии 8. В остальных случаях выдается пустая буква е. Отсюда получаем следующую отмеченную таблицу переходов.
Из построенной таблицы видно, что из состояний 0, 1, 3 и 5 автомат сигналами x 1 и x 2 переводится в одинаковые состояния (2 и 1). Кроме того, все перечисленные состояния отмечены одинаковыми выходными сигналами. Поэтому состояния 0, 1, 3 и 5 можно объединить в одно состояние, обозначив его как a 0. Введем обозначения: 2 – a 1, 4 – a 2, 6 – a 3, 7 – a 4, 8 – a 5. Тогда получим упрощенную таблицу переходов автомата. В этой таблице из состояний a 3 и a 4 под действием входных сигналов х 1 и х 2 автомат переходит в одинаковые состояния a 4 и a 5. Но объединять эти состояния нельзя, так как они отмечены разными выходными сигналами. По этой же причине нельзя объединять состояния a 0 и а 5. Объединение состояний и составляет второй этап минимизации, причем объединяются только такие состояния, которые отмечены одинаковыми выходными сигналами, и из которых под действием одинаковых входных сигналов происходит переход в одинаковые состояния. Очевидно, у таких состояний должны совпадать столбцы таблицы переходов.
Четвёртый этап минимизации В некоторых случаях после получения отмеченной таблицы переходов автомата возможен четвертый этап минимизации. Правда этот этап не всегда приводит к уменьшению числа состояний и часто является проверочным. Алгоритм этого этапа рассмотрим на примере. Пусть есть автомат, заданный следующей отмеченной таблицей переходов:
Алгоритм минимизации заключается в следующем: 1. Все внутренние состояния разбиваются на группы по числу выходных сигналов. В нашем случае есть два выходных сигнала y 1 и y 2 и, следовательно, будет две группы, которые мы обозначим буквами a и b. 2. 3.
4. Пользуясь таблицей переходов автомата, вновь отмечают каждое состояние последовательностью букв. Разделение состояний на новые группы продолжают до тех пор, пока новые группы состояний появляться не будут. В нашем случае минимизация заканчивается на втором шаге, так как все состояния, входящие в группы а и с, отмечены одинаковыми последовательностями букв, а группа b и d содержат только по одному состоянию. Все состояния, входящие в каждую из этих групп, можно заменить одним состоянием той же группы. Взяв в качестве представителей групп состояния 0, 1, 3 и 6 и обозначив их символами a 0, a 1, a 2 и a 3соответственно, получим следующую таблицу переходов с минимальным числом внутренних состояний.
Для построения автомата Мили воспользуемся рассмотренным ранее алгоритмом, для чего в каждую клетку совмещенной таблицы переходов и выходов запишем значения выходного сигнала, которым отмечено, находящееся здесь состояние.
В полученной таблице колонки, помеченные состояниями a 0 и a 2, a 1 и a 3 идентичны, что позволяет при минимизации исключить состояния a 2 и a 3. В результате получаем таблицу переходов и выходов автомата Мили, имеющего два состояния a 0 и a 1.
Основные понятия и определения В вычислительной технике используются схемы двух классов: комбинационные схемы и цифровые автоматы. Отличительной особенностью КС является наличие функциональной зависимости между входными и выходным сигналами: y(t) = f(x(t)). Причем при отсутствии входных сигналов выходные сигналы также отсутствуют, поскольку такие схемы не имеют памяти. В отличии КС схемы второго класса содержат в своем составе элементы памяти (запоминающие элементы). Эти схемы называются цифровыми автоматами (ЦА) или просто автоматами. В ЦА выходные сигналы в данный момент времени зависят не только от значения входных сигналов в тот же момент времени, но и от состояния схемы, которое, в свою очередь, определяется значениями входных сигналов, поступивших в предшествующие моменты времени. Введем основные понятия и определения. Автомат – это дискретный преобразователь информации, способный принимать различные состояния, переходить под воздействием входных сигналов из одного состояния в другое и выдавать различные выходные сигналы. Если множество состояний автомата, а так же множества входных и выходных сигналов конечны, то автомат называется конечным автоматом. Кодирование информации Информацию, поступающую на вход автомата, а так же выходную информацию, принято кодировать конечной совокупностью символов. Эту совокупность называют алфавитом, отдельные символы, образующие алфавит – буквами, а любые упорядоченные последовательности букв – словами в этом алфавите. Например: в алфавите X = (x1, x2), состоящем из двух букв, словами будут: x1, x2, x1x1, x1x2, x2x1, x2x2, x1x1x1 и т.д. Наряду со словами, состоящими не менее чем из одной буквы, введем слово, не содержащее ни одной буквы, которое будем обозначать символом е и называть пустым словом или пустой буквой. Математической моделью реального КА является абстрактный автомат, который имеет один входной канал и один выходной канал (рис. 4.1):
Рис. 4.1. Абстрактный автомат Автомат функционирует в дискретные моменты времени, интервал между которыми Т называется тактом. При этом в каждый дискретный момент времени на вход автомата поступает одна буква входного алфавита, автомат переходит из одного состояния в другое и выдается одна буква выходного алфавита. В зависимости от того, как задается длительность такта Т, различают автоматы синхронного действия (T = const) и асинхронного действия (T≠ const). Мы будем рассматривать, в основном, синхронные автоматы, функционирующие в дискретные моменты времени, которые можно обозначить целыми неотрицательными натуральными числами t = 0, 1, 2, 3, …, имеющими смысл номера такта. Для задания любого КА S необходимо задавать совокупность из пяти объектов: S{A, X, Y, d, l}, где A = {a0, a1, a2,..., am,..., aM} – множество состояний автомата, X = {x1, x2, …, xf,…, xF} – множество входных сигналов или входной алфавит, Y = {y1, y2, …, yg,…, yG} – множество выходных сигналов или выходной алфавит, d – функция переходов, определяющая состояние автомата в момент времени (t + 1) в зависимости от состояния автомата и входного сигнала в момент времени t, т.е. a(t + 1) = d [a(t), x(t)], 1 – функция выходов, определяющая значение выходного сигнала в зависимости от состояния автомата и входного сигнала в тот же момент времени, т.е. y(t) = l[a(t), x(t)]. Если множества А, Х и У конечны, то автомат называется конечным. Автомат работает следующим образом. В каждый момент времени t он находится в определенном состоянии a(t) из множества А возможных состояний, причем в начальный момент времени t = 0 он находится в состоянии a0. Автомат воспринимает входной сигнал x(t), выдает выходной сигнал y(t) = l[a(t), x(t)] и переходит в состояние a(t + 1) = d[a(t), x(t)]. Другими словами, абстрактный автомат каждой паре символов a(t) и x(t) ставит в однозначное соответствие пару символов a(t + 1) и y(t). Такие автоматы называют детерминированными.
©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.
|
, состоящее из всех слов, полученных приписыванием к каждому слову события S 1 каждого слова события S 2, затем слова события S 3 и т.д.
= (x 1 x 2, x 1 x 1 x 2, x 2 x 1 x 2, x 1 x 1 x 2, x 1 x 1 x 1 x 2, x 2 x 1 x 1 x 2). Произведение событий не коммутативно, т.е. 
. Поэтому следует различать операции «умножение справа» и «умножение слева». Например, относительно произведения событий 
можно сказать, что событие S 2 умножено на событие S 1 справа, а событие S 1 на S 2 – слева.
.
– законы ассоциативности;
– закон дистрибутивности;
;
По таблице переходов автомата определяют, к каким группам принадлежат внутренние состояния, в которые автомат переходит из данного состояния под воздействием каждой буквы входного алфавита. Эти состояния запишем в виде последовательности букв под каждым из состояний автомата. Например, из состояния 0 автомат переходит в состояния 2, 3 и 1, которые принадлежат соответственно к следующим группам a, b и a. Эта последовательность букв (aba) и записывается под состоянием 0:
Проводят новое разделение внутренних состояний на группы, объединяя в каждой группе состояния, отмеченные одинаковой последовательностью букв. В нашем случае каждая из двух групп распадается на две группы, по числу различных последовательностей букв:
