2014-02-09
2330
Раздел 5. Лекция 13. Абстрактный синтез конечных автоматов
При синтезе комбинационных схем можно составить таблицу зависимости значения выходного сигнала от комбинации входных. Такая таблица однозначно определяет систему переключательных функций, описывающую работу комбинационной схемы. Составить аналогичную таблицу, описывающую работу конечного автомата (КА), не представляется возможным, так как множество допустимых входных слов автомата, вообще говоря, бесконечно. Поэтому для задания КА и используются таблицы переходов и выходов, которые позволяют представить соответствие между бесконечными множествами входных и выходных слов конечными таблицами. В связи с этим, прежде чем приступить к синтезу схемы КА, необходимо составить таблицу переходов и выходов, что не всегда является простым делом особенно в тех случаях, когда алгоритм работы автоматов задан в описательной форме. Для того чтобы упростить и формализовать процедуру построения таблиц переходов и выходов, необходимо ввести такую исходную форму задания автоматов, переход к которой от алгоритмов, сформулированных в описательной форме, не представляет трудностей. Мы рассмотрим один из возможных способов формального задания автоматов, а именно, задание автомата на языке регулярных событий.
|
|
|
В основе рассматриваемого способа задания автоматов, лежит понятие событий, представимых в автоматах.
Пусть Y { y 1, y 2, …, y k} – выходной алфавит конечного автомата S с фиксированным начальным состоянием a 0. Тогда каждой букве y j, выходного алфавита можно поставить в соответствие множество входных слов S j(x 1, x 2,…, x m), которые вызывают появление на выходе автомата буквы yj. Определенное таким образом множество слов S j(x 1, x 2, …, x m) называют событием, представленным в автомате выходным сигналом y j.
Поэтому для задания конечного автомата, имеющего выходной алфавит Y { y 1, y 2, …, y k}, достаточно разбить множество всех возможных входных слов на K событий S 1, S 2, …, S k, представленных в автомате выходными сигналами y 1, y 2, …, y k соответственно. Для частичного автомата необходимо, кроме того, задать множество S з запрещенных слов. Таким образом, конечный автомат может быть задан таблицей, устанавливающей соответствия между событиями и буквами выходного алфавита. Зная набор событий S j, можно, не пользуясь таблицами переходов и выходов, найти реакцию автомата на любое входное слово, для чего достаточно определить множество каких слов входного алфавита оно входит (то есть какому событию принадлежит).
Для описания автоматов на языке регулярных событий вводят ряд операций над событиями, то есть строят алгебру событий. Мы рассмотрим алгебру событий, введенную Клини и усовершенствованную академиком Глушковым В. М.
|
|
|
Соответствие событий буквам выходного алфавита
| Событие | Буква |
| S1(x1, x2,…, xm) S2(x1, x2,…, xm) … Sk(x1, x2,…, xm) Sз(x1, x2,…, xm) | y1 y2 … yk - |
Операции в алгебре событий. Алгебра событий включает три операции: дизъюнкцию (объединение) событий, произведение событий и итерацию событий.
Дизъюнкцией событий называют событие S = S 1v S 2v…v S k, состоящее из всех слов, входящих в события S 1, S 2, …, S k.
Пример:
Событие S 1 содержит слова x 1, x 2 x 1, x 1 x 1, т.е. S 1 = (x 1, x 2 x 1, x 1 x 1), а
S 2=(x 2, x 1 x 2). Тогда S = S 1 v S 2 = (x 1, x 2, x 1 x 1, x 1 x 2 x 2 x 1).
Произведением событий называется событие S = S 1* S 2* …,* S k, состоящее из всех слов, полученных приписыванием к каждому слову события S 1 каждого слова события S 2, затем слова события S 3 и т.д.
Пример:
S 1 и S 2 те же. Тогда S = S 1* S 2 = (x 1 x 2, x 1 x 1 x 2, x 2 x 1 x 2, x 2 x 1 x 1 x 2, x 1 x 1 x 2, x 1 x 1 x 1 x 2). Произведение событий не коммутативно, то есть слова, входящие в события S 1* S 2 и S 2 *S 1 различны: то есть S 1 *S 2 
S 2 *S 1. Поскольку произведение не коммутативно, следует различать операции «умножение справа» и «умножение слева». Например, относительно произведения событий S 1 *S 2 можно сказать, что событие S 2 умножено на событие S 1 справа, а событие S 1 на S 2 – слева.
Третьей операцией, применяемой в алгебре событий, является одноместная операция итерация, которая применима только к одному событию. Для обозначения итерации вводят фигурные скобки, которые называются итерационными.
Итерацией события S называется событие{ S }, состоящее из пустого слова e и всех слов вида S, SS, SSS и т.д. до бесконечности. То есть:
{ S } = e v S v SS v SSS v …
Пример:
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, …, x m).
Регулярное событие – это любое событие, которое можно получить из букв данного алфавита с помощью конечного числа операций дизъюнкции, произведения и итерации. Регулярное выражение – любое выражение, составленное с помощью операций дизъюнкции, произведения и итерации.
