ВходСпособы описания конечных автоматов. Автоматы Способы задания Основные определения n Конечным Стандартные или автоматные языки описания
Можно выделить два класса языков для описания функционирования цифровых автоматов: начальные языки и стандартные или автоматные языки.
Начальные языки задают функцию переходов и функцию выходов в неявном виде. Поведение автомата описывается в терминах входных и выходных последовательностей, реализуемых оператором, или последовательностей управляющих сигналов, воздействующих на управляющий автомат.
Для описания функционирования абстрактных ЦА на начальном языке можно использовать:
Язык регулярных выражений алгебры событий;
Язык исчисления предикатов;
Язык логических схем алгоритмов (ЛСА);
Язык граф схем алгоритмов (ГСА).
Язык ГСА совместно с языком ЛСА называют одним общим термином: язык операторных схем алгоритмов (ОСА). На практике наиболее часто используется язык ГСА.
3.3.1 Задание цифровых автоматов на стандартных
языках
Стандартные или автоматные языки
задают функции переходов выходов в явном виде. К ним относятся таблицы, графы, матрицы переходов и выходов и их аналитическая интерпретация. Для того, чтобы задать автомат, необходимо описать все компоненты вектора
S =
(A, Z, W, d, l, a
1).
При табличном способе задания
автомат Мили описывается с помощью двух таблиц: таблицы переходов и таблицы выходов. Таблица переходов задает функцию d
(табл.3.4.), таблица выходов функцию - l
(табл.3.5.). Каждому столбцу табл.3.4 и 3.5 поставлено в соответствие одно состояние из множества А
, каждой строке – один входной сигнал из множества Z
. На пересечении столбца a m
и строки z f
в табл.3.4 записывается состояние
a s
, в которое должен перейти автомат из состояния a m
, под действием входного сигнала z f
, т.е. a s = d
(a m , z f
).
На пересечении столбца a m
и строки z f
в табл.3.5 записывается выходной сигнал w g
, выдаваемый автоматом в состоянии a m
при поступлении на его вход сигнала z f
, т.е.
w g = l
(a m , z f
).
Таблица 3.4 Таблица 3.5
| Таблица переходов автомата Мили | Таблица выходов автомата Мили | |||||||||
| a 1 | a 2 | a 3 | a 4 | a 1 | a 2 | a 3 | a 4 | |||
| z 1 | a 2 | a 2 | a 1 | a 1 | z 1 | w 1 | w 1 | w 2 | w 4 | |
| z 2 | a 4 | a 3 | a 4 | a 3 | z 2 | w 5 | w 3 | w 4 | w 5 |
Для указанных таблиц А =
{ a
1 , a
2 , a
3 , a
4 }; Z =
{ z
1 , z
2 };
W =
{w
1 , w
2 , w
3 , w
4 , w
5 }.
Автомат Мили может быть задан также одной совмещенной таблицей переходов и выходов (табл.3.6), в которой каждый элемент a s /w g , записанный на пересечении столбца a m и строки z f , определяется следующим образом:
a s = d (a m , z f ); w g = l (a m , z f ).
Автомат Мура задается одной отмеченной таблицей переходов (табл.3.7), в которой каждому столбцу приписаны не только состояния a m
, но еще и выходной сигнал w g
, соответствующий этому состоянию, где w g = l
(a m
). Для табл. 3.7 A =
{a
4 , a
2 , a
3 , a
4 }; Z =
{z
1 , z
2 };
W =
{w
1 , w
2 , w
3 }.
Одним из преимуществ этого способа задания является то, что любая таблица переходов и выходов задает конечный автомат. При этом должны удовлетворяться два условия:
Условие однозначности (детерминированности), которое означает, что для любой пары a m z f задано единственное состояние перехода a s и единственный выходной сигнал w g , выдаваемый на переходе.
Условие полной определенности , которое означает, что для всех возможных пар a m z f всегда указано состояние и выходной сигнал.
Таблица 3.6 Таблица 3.7
| Совмещенная таблица переходов и выходов автомата Мили | Отмеченная таблица переходов и выходов автомата Мура | |||||||||
| a 1 | a 2 | a 3 | a 4 | w 3 | w 2 | w 3 | w 1 | |||
| z 1 | a 2 /w 1 | a 2 /w 1 | a 1 /w 2 | a 1 /w 4 | a 1 | a 2 | a 3 | a 4 | ||
| z 2 | a 4 /w 5 | a 3 /w 3 | a 4 /w 4 | a 3 /w 5 | z 1 | a 1 | a 3 | a 1 | a 4 | |
| z 2 | a 2 | a 4 | a 4 | a 1 |
Автомат называется неполностью определенным или частичным , если либо функция d определена не на всех парах (a m z f ) Î A x Z , либо функция l определена не на всех указанных парах в случае автомата Мили и на множестве не всех внутренних состояний для автомата Мура. Для частичных автоматов Мили и Мура в рассмотренных таблицах на месте неопределенных состояний и выходных сигналов ставится прочерк.
Граф автомата – это ориентированный граф, вершины которого соответствуют состояниям, а дуги – переходам между ними. Дуга, направленная из вершины a m в вершину a s , задает переход в автомате из состояния a m в состояние a s . В начале этой дуги записывается входной сигнал z f Î Z , вызывающий данный переход: a s = d (a m , z f ). Для графа автомата Мили выходной сигнал w g Î W , формируемый на переходе, записывается в конце дуги, а для автомата Мура рядом с вершиной, отмеченной состоянием a m , в котором он формируется. Если переход в автомате из состояния a m в состояние a s производится под действием нескольких входных сигналов, то дуге графа, направленной из a m в a s , приписываются все эти входные и соответствующие выходные сигналы. Графы автоматов Мили и Мура, построенные по табл.3.6 и 3.7 приведены соответственно на рис.3.7. а, б.
Применительно к графу условия однозначности и полной определенности будут заключены в следующем:
Не существует двух ребер с одинаковыми входными пометками, выходящих из одной и той же вершины;
Для всякой вершины a m и для всякого входного сигнала z f имеется такое ребро, помеченное символом z f , которое выходит из a m .
Рис.3.7. Графы автоматов: a – Мили; б – Мура
При задании графов с большим числом состояний и переходов наглядность теряется, поэтому оказывается предпочтительным задавать этот граф в виде списка – таблицы переходов.
Прямая таблица переходов – таблица, в которой последовательно перечисляются все переходы сначала из первого состояния, затем из второго и т.д. Табл.3.8 – прямая таблица переходов автомата Мили, построенная по графу, приведенному на рис.3.7.а.
В ряде случаев оказывается удобным пользоваться обратной таблицей переходов, в которой столбцы обозначены точно так же, но сначала записываются все переходы в первое состояние, затем во второе и т.д. Табл.3.9 – обратная таблица переходов автомата Мили, построенная по графу, приведенному на рис.3.7,а.
Как и граф таблицы переходов должны удовлетворять условиям однозначности и полноты переходов.
| Таблица 3.8 Прямая таблица переходов автомата Мили | Таблица 3.9 Обратная таблица переходов автомата Мили | |||||||
| a m (t ) | z f (t ) | a s (t+ 1) | w g (t ) | a m (t ) | z f (t ) | a s (t+ 1) | w g (t ) | |
| a 1 | z 1 | a 2 | w 1 | a 3 | z 1 | a 1 | w 2 | |
| z 2 | a 4 | w 5 | a 4 | z 1 | w 4 | |||
| a 2 | z 1 | a 2 | w 1 | a 1 | z 1 | a 2 | w 1 | |
| z 2 | a 3 | w 3 | a 2 | z 1 | w 1 | |||
| a 3 | z 1 | a 1 | w 2 | a 2 | z 2 | a 3 | w 3 | |
| z 2 | a 4 | w 4 | a 4 | z 2 | w 5 | |||
| a 4 | z 1 | a 1 | w 4 | a 1 | z 2 | a 4 | w 5 | |
| z 2 | a 3 | w 5 | a 3 | z 2 | w 4 |
Прямая таблица переходов автомата Мура строится так же как и для автомата Мили. Разница лишь в том, что выходной сигнал w g (t ) приписывается состоянию автомата a m (t ) (табл. 3.10), либо выходной сигнал w g (t a s (t+ 1) (табл. 3.11).
Обратная таблица переходов автомата Мура строится так же как и для автомата Мили. Разница лишь в том, что выходной сигнал w g (t +1) приписывается состоянию автомата a s (t+ 1) (табл. 3.12).
В некоторых случаях для задания автомата используются матрицы переходов и выходов , которые представляют собой таблицу с двумя входами. Строки и столбцы таблицы отмечены состояниями. Если существует переход из a m под действием z f в a s с выдачей w g , то на пересечении строки a m и столбца a s записывается пара z f w g . Ясно, что не всякая матрица задает автомат. Как граф и таблица переходов и выходов она должна удовлетворять условиям однозначности и полноты переходов.
| Таблица 3.10 Прямая таблица переходов автомата Мура Вариант 1 | Таблица 3.11 Прямая таблица переходов автомата Мура Вариант 2 | |||||||
| a m (t ) | w g (t ) | z f (t ) | a s (t+ 1) | a m (t ) | z f (t ) | a s (t+ 1) | w g (t +1) | |
| a 1 | w 3 | z 1 | a 1 | a 1 | z 1 | a 1 | w 3 | |
| z 2 | a 2 | z 2 | a 2 | w 2 | ||||
| a 2 | w 2 | z 1 | a 3 | a 2 | z 1 | a 3 | w 3 | |
| z 2 | a 4 | z 2 | a 4 | w 1 | ||||
| a 3 | w 3 | z 1 | a 1 | a 3 | z 1 | a 1 | w 3 | |
| z 2 | a 4 | z 2 | a 4 | w 1 | ||||
| a 4 | w 1 | z 1 | a 4 | a 4 | z 1 | a 4 | w 1 | |
| z 2 | a 1 | z 2 | a 1 | w 3 |
| Таблица 3.12 Обратная таблица переходов автомата Мура Вариант 2 | |||
| a m (t ) | z f (t ) | a s (t+ 1) | w g (t +1) |
| a 1 | z 1 | a 1 | w 3 |
| a 3 | z 1 | ||
| a 4 | z 2 | ||
| a 1 | z 2 | a 2 | w 2 |
| a 2 | z 1 | a 3 | w 3 |
| a 2 | z 2 | a 4 | w 1 |
| a 3 | z 2 | ||
| a 4 | z 1 |
Системы канонических уравнений (СКУ) и системы выходных функций (СВФ) являются аналитической интерпретацией таблиц переходов и выходов или графов автоматов. СКУ – определяет функции переходов ЦА, а СВФ – определяет функции выходов ЦА.
Каждое состояние ЦА интерпретируется как событие, соответствующее множеству переходов в это состояние:
Для сокращения записи СКУ и СВФ будем в дальнейшем везде, где это возможно, опускать знаки конъюнкции и времени t в правой части уравнений типа (3.10).
Для автомата Мили, заданного табл.3.8 или табл. 3.9 запишем СКУ и СВФ (3.811и 3.12. соответственно):
| a 1 (t +1) = z 1 a 3 Ú z 1 a 4 ; a 2 (t +1) = z 1 a 1 Ú z 1 a 2 ; a 3 (t +1) = z 2 a 2 Ú z 2 a 4 ; a 4 (t +1) = z 2 a 1 Ú z 2 a 3 . | (3.11) | w 1 (t ) = z 1 a 1 Ú z 1 a 2 ; w 2 (t ) = z 1 a 3 ; w 3 (t ) = z 2 a 2 ; w 4 (t ) = z 1 a 4 Ú z 2 a 3; w 5 (t ) = z 2 a 1 Ú z 2 a 4. | (3.12) |
Запишем СКУ и СВФ для автомата Мура, заданного табл. 3.10 - 3.12, (3.13 и 3.14 соответственно).
Для описания конечных цифровых автоматов можно использовать стандартные (автоматные) языки и начальные языки.
Стандартные или автоматные языки описания.
Они описывают функции переходов и выходов в явном виде, а именно в виде:
Таблиц переходов и выходов;
Из определения автомата следует, что его всегда можно задать таблицей с двумя входами, содержащей m строк и n столбцов, где на пересечении столбца q(состояния автомата) и строки а (входные сигналы) стоят значения функций φ(l) (a i ,q j) (функция переходов); \|/ (m )(a i ,q j)(функция выходов).
Таблица 1
2) графа, представляющего наглядно функции l и m ..
Другой способ задания конечного автомата - графический. При этом способе состояния автомата изображают кружками, в которые вписывают символы состояний q j (j= 1,..., п). Из каждого кружка проводится m стрелок
(ориентированных рёбер) взаимно-однозначно соответствующих символам входного алфавита X(V). Стрелке, соответствующейбукве а i X и выходящей из кружка q j Q(S), приписывается пара (а i , \|/ (a i ,q j) , причем эта стрелка ведет в кружок, соответствующий φ (a i ,q j)
Полученный рисунок называется графом автомата или, диаграммой Мура. Для не очень сложных автоматов этот способ более нагляден, чем табличный.
Автомат Мура
Абстрактный автомат Мура это частный случай автомата Мили (4), когда выходной символ зависти только от состояния автомата, а именно функция выходов автомата Мура:
w =m (s ) (5)
Для каждого автомата Мили можно построить эквивалентный автомат Мура, реализующий точно такой же алфавитный оператор. Пусть A = <V,W,S,l,m,s (0)> автомат Мили. В качестве состояний эквивалентного автомата Мура возьмем пары . Тогда функция выходов эквивалентного автомата Мура
а функция переходов
Задание конечного автомата системой булевых функций
Третий способ задания конечного автомата А = (X;Q;Y; φ ;\|/), заданного таблицей или диаграммой Мура, состоит в определении системы булевых функций.
X-входной алфавит;
Q-множество состояний автомата;
Y-выходной алфавит;
φ -функция перехода;
\|/-функция выходов.
Изложим алгоритм этого способа задания.
1.Находим числа k, r, s,
удовлетворяющие условиям 2 k -1 < т
< 2 k ;
2 r
- 1 < п ≤ 2 r ;
2 s - 1
Очевидно, что k,r, s соответственно равны числу разрядов в двоичном представлении чисел т, п, р. Например, если т - 5, п = 17, р = 3, то k= 3, r= 5,s = 2.
2. Кодирование состояний входных и выходных символов исходного
автомата.
Каждому q j Q взаимно-однозначно ставим в соответствие двоичную последовательность длины r - двоичный код = z 1 z 2 z r . Аналогично каждому а i X и b k Y ставим взаимно однозначно в соответствие двоичные последовательности =x 1 x 2 x k ; =y 1 y 2 y s .
Отметим, что кодирование состояний, входных и выходных символов можно провести многими способами. При этом некоторые последовательности (коды) могут оказаться неиспользованными.
| . |
3.Составляем следующую таблицу:
Эта таблица содержит k + r + r + s столбцов и 2 k + r строк. В первых k + r столбцах выписаны все наборы длины k + r. Каждый такой набор соответствует паре (), где -возможный код некоторого состояния, код входного символа.
4.Заполнение последних столбцов в таблице (предыдущий шаг).
Для каждой пары (a i ,q j), где а i X; q j Q, находим код и . По таблице автомата (или диаграмме Мура) определяем и \|/(а; q) = Y. Затем находим код = " 1 " 2 ... ",. и код .
В строку таблицы соответствующую набору
дописываем набор
5. Определение системы булевых функций.
После выполнения предыдущего шага может оказаться, что все строки в таблице заполнены. Это произойдет в том случае, если хотя б одно из чисел m, n не является степенью 2. Таким образом, функции окажутся не полностью определенными – на некоторых наборах их значения не определены. Тогда мы их доопределяем произвольным образом. Как правило, доопределение функций проводят так, чтобы получившиеся полностью определенные функции удовлетворяли тем или иным условиям оптимальности, например представлялись минимальными ДНФ.
После выполнения этого шага исходный автомат будет задавать системой полностью определенных булевых функций
3.2 Начальные языки .
Они описывают автомат на поведенческом уровне. К начальным языкам относятся:
1) языки логических схем и граф схем алгоритмов;
2) язык регулярных выражений алгебры событий;
3) формальные и автоматные грамматики.
Если задано описание (4) полностью определенного автомата в стандартной форме, то для любого начального состояния автомата s (0) и последовательности входных символов v (0)v (1)v (2)…v (t ) можно вычислить реакцию автомата в виде последовательности выходных символов w (0)w (1)…w (t ).
Примеры.
Пример 1 . Автомат ПРОДАВЕЦ газет получает монеты достоинством в 1 рубль и 2 рубля. Если сумма монет равна 3 рублям, то автомат выдает газету. Если сумма больше 3 рублей, то автомат возвращает все деньги. Введем обозначения входных и выходных символов и состояний автомата.
Входные символы:
v 1 - опущена монета достоинством 1 рубль;
v 2 - опущена монета достоинством 2 рубля.
Выходные символы:
w 1 - сообщение "Принята сумма 1 руб.";
w 2 - сообщение "Принята сумма 2 руб.";
w 3 - выдача газеты;
w 4 - возврат денег.
Состояния автомата:
s 0 - принята сумма 0 руб. (начальное состояние);
s 1 - принята сумма 1 руб.;
s 2 - принята сумма 2 руб.
Функцию переходов представим таблицей 2, а функцию выходов - таблицей 3.
Этот же автомат можно задать в виде отмеченного орграфа, вершины которого соответствуют состояниям автомата, а дуги - переходам (рис.3).
|
Ниже приведен пример реакции автомата ПРОДАВЕЦ на входную последовательность v 1 v 1 v 2 v 2 v 1 v 2 v 2 v 1 v 1 v 1 …:
| t | … | |||||||||||
| v(t) | … | v 1 | v 1 | v 2 | v 2 | v 1 | v 2 | v 2 | v 1 | v 1 | v 1 | … |
| s(t) | … | s 0 | s 1 | s 2 | s 0 | s 2 | s 0 | s 2 | s 0 | s 1 | s 2 | s 0 |
| w(t) | … | w 1 | w 2 | w 4 | w 2 | w 3 | w 2 | w 4 | w 1 | w 2 | w 3 | … |
Пример 2. Для рассмотренного выше автомата ПРОДАВЕЦ можно построить эквивалентный автомат Мура, характеризуемый таблицей переходов/выходов (табл 4).
Таблица 4
| Новое состояние | |
| Входной символ | Текущее состояние/выходной символ |
| v 1 v 2 | s 1 v 1 s 2 v 1 s 2 v 1 s 0 v 1 s 0 v 1 s 0 v 1 s 1 v 2 s 2 v 2 s 2 v 2 s 0 v 2 s 0 v 2 s 0 v 2 |
На рис.4 представлен граф переходов/выходов автомата ПРОДАВЕЦ, соответствующий табл.4. Начальное состояние эквивалентного автомата Мура включает входной символ v (0). Поэтому приходится смещать поток входных символов: .
Пример 3. Обозначим состояние автомата Мура, соответствующее паре (s i ,v j) автомата Мили через s ij . Тогда реакция эквивалентно автомата ПРОДАВЕЦ на последовательность v 1 v 1 v 2 v 2 v 1 v 2 v 2 v 1 v 1 v 1 … будет:
| t | … | ||||||||||
| … | v 1 | v 2 | v 2 | v 1 | v 2 | v 2 | v 1 | v 1 | v 1 | … | |
| … | s 01 | s 11 | s 12 | s 02 | s 21 | s 02 | s 22 | s 01 | s 11 | s 21 | |
| w(t) | … | w 1 | w 2 | w 4 | w 2 | w 3 | w 2 | w 4 | w 1 | w 2 | … |
Опишем поведение родителя, отправившего сына в школу. Сын приносит двойки и пятерки. Отец не хочет хвататься за ремень каждый раз, как только сын получит очередную двойку, и выбирает более тонкую тактику воспитания. Задавать автомат удобно графом, в котором вершины соответствуют состояниям, а ребро из состояния s в состояние q, помеченное х/у, проводится тогда, когда автомат из состояния s под воздействием входного сигнала х переходит в состояние q с выходной реакцией у. Граф автомата, моделирующего умное поведение родителя, представлен на рис. 5.
Рис. 5. Автомат, описывающий поведение «умного» отца
Этот автомат имеет четыре состояния {s0, s1, s2, s3} и два входных сигнала - оценки, полученные сыном в школе: {2,5}. Начиная с начального состояния s0(оно помечено входной стрелкой), автомат под воздействием входных сигналов переходит из одного состояния в другое и выдает выходные сигналы - реакции на входы. Выходы автомата {у0,..., у5} будем интерпретировать как действия родителя так:
y0: - брать ремень;
yl: - ругать сына;
у2: - успокаивать сына;
уЗ: - надеяться;.
у4: - радоваться;
у5: - ликовать.
Сына, получившего одну и ту же оценку - двойку, ожидает дома совершенно различная реакция отца в зависимости от предыстории его учебы. Отец помнит, как его сын учился раньше, и строит свое воспитание с учетом его предыдущих успехов и неудач. Например, после третьей двойки в истории 2,2, 2 сына встретят ремнем, а в истории 2, 2, 5, 2 - будут успокаивать. Каждая предыстория определяет текущее состояние автомата, при этом некоторые входные предыстории эквивалентны (именно те, которые приводят автомат в одно и то же состояние): история 2, 2, 5 эквивалентна пустой истории, которой соответствует начальное состояние.
Текущее состояние автомата представляет все то, что автомат знает о прошлом с точки зрения его будущего поведения - реакций на последующие входы. Эта история в концентрированном виде определена текущим состоянием, и все будущее поведение автомата, как реакция его на последующие входные сигналы, определено именно текущим состоянием, но не тем, как автомат пришел в него.
Итак, конечный автомат - это устройство, работающее в дискретные моменты времени (такты). На вход конечного автомата в каждом такте поступает один из возможных входных сигналов, а на его выходе появляется выходной сигнал, являющийся функцией его текущего состояния и поступившего входного сигнала. Внутреннее состояние автомата также меняется. Моменты срабатывания (такты) определяются либо принудительно тактирующими синхросигналами, либо асинхронно, наступлением внешнего события - прихода сигнала.
Определим конечный автомат формально.
Кроме графического представления для автомата можно использовать и табличное, задавая функции переходов и выходов в виде таблиц. Автомат примера будет представлен следующими таблицами.
Таблица 5, а определяет функцию переходов так:
а табл. 5, б определяет функцию выходов : .(s0, 2) = у2; (s2, 5) = у3; ....
Комбинационные схемы, хотя и позволяют реализовать любые фиксированные зависимости между входными и выходными сигналами, не могут изменять характера своего поведения (т.е. последовательности обработки данных) - любое такое изменение требует изменения структуры схемы, т.е., по сути, переходу к другой схеме. Решить проблему перестройки работы без изменения структуры схемы возможно, если ввести в нее элементы памяти, которые позволяли бы фиксировать и сохранять промежуточные состояния устройства - в этом случае выходной сигнал будет зависеть не только от входного сигнала, но и от состояния схемы. Если количество таких элементов конечно, то, как указывалось выше, дискретное устройство будет называться конечным автоматом.
Конечным автоматом
называется система
Как указывалось ранее, Y(x,q) задает порядок преобразования входных символов и состояния автомата на предыдущем такте в состояние на последующем, a Q(x,q) - преобразования входных символов и состояния автомата на текущем такте в выходной символ. Если q 0 - начальное состояние автомата, а i - номер такта, то его работа описывается системой:
Данные соотношения получили название системы канонических уравнений конечного автомата. Пользуясь ими можно, начиная с q 0 , последовательно находить все последующие состояния автомата и выходные символы.
Выделяются два типа автоматов - инициальные и неинициальные. В инициальных автоматах начальное состояние фиксировано (т.е. они всегда начинают работать из одного и того же состояния q 0). В неинициальных автоматах в качестве начального состояния может быть выбрано любое из множества Q ; этим выбором определяется дальнейшее поведение автомата.
Представление конкретного конечного автомата фактически сводится к описанию задающих его автоматных функций. Из системы (9.3) следует, что при конечном числе возможных внутренних состояний количество возможных значений автоматных функции также оказывается конечным. Их описание возможно различными способами, наиболее распространенными из которых является табличный и с помощью диаграмм.
В табличном способе автоматные функции задаются двумя конечными таблицами, именуемыми соответственно матрицей переходов и матрицей выходов. В этих таблицах строки обозначаются буквами входного алфавита, а столбцы - буквами внутреннего алфавита (символами, кодирующими внутреннее состояние автомата). В матрице переходов на пересечении строки (x k) и столбца (q r) помещаются значения функции Y (q r , x k), а в матрице выходов - значения функции Q(q r , x k).
ПЛАН ЛЕКЦИИ
1. Табличный способ
2. Графический способ задания автомата
Чтобы задать конечный автомат S, необходимо описать все элементы множества S = {A, X, Y, d , l } , т.е. необходимо описать входной, выходной алфавиты и алфавит состояний, а также функции переходов d и выходов l . При этом среди множества A = {a 0 ,a 1 ,…, a n } необходимо выделить начальное состояния a0, в котором автомат находится в момент времени t = 0. Существует несколько способов задания работы автомата, но наиболее часто используются табличный и графический.
- Табличный способ
При этом способе автомат Мили описывается двумя таблицами: таблицей переходов и таблицей выходов.
Таблица переходов
|
x j \a j |
|||
|
d (a 0 ,x 1) |
d (a n ,x 1) |
||
|
x m |
d (a 0 ,x m) |
d (a n ,x m ) |
Таблица выходов
|
x j \a j |
|||
|
l (a 0 ,x 1) |
l (a n ,x 1) |
||
|
x m |
l (a 0 ,x m) |
l (a n ,x m ) |
Строки этих таблиц соответствуют входным сигналам x (t ), а столбцы – состояниям. На пересечении столбца a i и строки x j в таблице переходов ставится состояние a s = d [ a i ,x j ], в которое автомат перейдет из состояния a i под воздействием сигнала x j ; а в таблице выходов – соответствующий этому переходу выходной сигнал y g = l [ a i ,x j ].
Совмещенная таблица переходов и выходов автомата Мили:
|
x j \a i |
|||
|
d (a 0 ,x 1)/ l (a 0 ,x 1) |
d (a n ,x 1)/ l (a n ,x 1) |
||
|
x m |
d (a 0 ,x m)/ l (a 0 ,x m) |
d (a n ,x m )/ l (a n ,x m ) |
Задание таблиц переходов и выходов полностью описывает работу конечного автомата, поскольку задаются не только сами функции переходов и выходов, но и также все три алфавита: входной, выходной и алфавит состояний.
Для задания автомата Мура требуется одна таблица, поскольку в этом автомате выходной сигнал однозначно определяется состоянием автомата.
Отмеченная таблица переходов автомата Мура :
|
y g |
l (a 0) |
l (a n) |
|
|
x j \a c |
|||
|
d (a 0 ,x 1) |
d (a n ,x 1) |
||
|
x m |
d (a 0 ,x m) |
d (a n ,x m ) |
Автомат Мили
|
x j \a i |
||||
|
a 1 /y 1 |
a 2 /y 3 |
А 3 /y 2 |
a 0 /y 1 |
|
|
a 0 /y 2 |
a 0 /y 1 |
A 3 /y 1 |
a 2 /y 3 |
Автомат Мура
|
x j \x j |
|||||
В этой таблице каждому столбцу приписан, кроме состояния a i , еще и выходной сигнал y (t ) = l (a (t )), соответствующий этому состоянию. Таблица переходов автомата Мура называется отмеченной потому, что каждое состояние отмечено выходным сигналом.
Приведем примеры табличного задания автоматов Мили и Мура :
По этим таблицам можно найти реакцию автомата на любое входное слово. Например.
Для автомата Мили:Для автомата Мура :
x 1 x 2 x 2 x 2 x 1 …x 1 x 2 x 2 x 2 x 1 …
a 0 a 1 a 0 a 0 a 0 a 1 a 0 a 2 a 4 a 1 a 4
y 1 y 1 y 2 y 2 y 1 y 2 y 1 y 2 y 1 y 2
2. Графический способ задания автомата (задание автомата с помощью графа)
Этот способ основан на использовании ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги – переходам между ними. Две вершины графа a i и a s соединяются дугой, направленной от a i к a s , если в автомате имеется переход из a i в a s , т.е. a s =d (a i , x j ). В автомате Мили дуга отмечается входным сигналом x j , вызвавшим переход, и выходным сигналом y g , который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние. Например, для автомата Мили, приведенного выше, граф имеет вид а), а для автомата Мура вид б).
Элементы теории автоматов
План:
1. Понятие автомата, принцип работы автомата
2. Способы задания конечных автоматов
3. Общие задачи теории автоматов
Теоретические сведения
Человек всегда стремился к тому, что бы облегчить свой труд, заставляя работать на себя некоторые механические устройства без собственного вмешательства. Вначале это были сказки, затем они стали превращаться в обыденные вещи. Автомобиль, телевизор, стиральные машины, целые производства работают без участия человека. Причем, вмешательство человека в большинстве случаев не требуется, а в ряде случаев, такое вмешательство может привести к негативным явлениям. Понятие «автомат», как некоторое устройство, выполняющее определенный вид действий давно трактуется людьми именно так.
Понятие автомата, принцип работы автомата
Понятие автомат рассматривается в двух аспектах:
1. Автомат – устройство , выполняющее некоторые функции без непосредственно участия человека. Автомат это реальное устройство, понятное, почему и как оно работает, хотя бы для тех людей, которые его сконструировали и изготовили. Автомобиль, трактор, самолет, светофор, телевизор, телефон – все это автоматы. В этом аспекте ЭВМ следует понимать как автомат, который работает по программе, составленной человеком.
2. Автомат – математическое понятие , обозначающее математическую модель реальных технических устройств. Автомат это абстрактное устройство, непонятно почему и как оно работает и, вообще, почему оно может работать. В этом аспекте автомат есть «черный ящик», который теоретически способен проводить некоторые действия. С точки зрения математики, абсолютно неважно что, как и почему производит те или иные действия.
Любой автомат должен иметь некоторое количество входов, некоторое количество выходов и некоторое количество внутренних состояний.
Алгебраическая теория автоматов является разделом теоретической кибернетики, который изучает дискретные автоматы с абстрактной алгебраической точки зрения.
Общая теория автоматов содержит различные подразделы. В зависимости от предмета изучения она делится на абстрактную теорию автоматов и структурную теорию автоматов.
Абстрактная теория автоматов изучает переходы, совершаемые автоматом, на который воздействуют входные сигналы, а также выходные сигналы как результат этих переходов.
Предметом изучения структурной теории автоматов является структура автомата, а также структура входных и выходных сигналов, например, способы кодирования входных и выходных сигналов и др.
Определение конечных автоматов
Автомат - абстрактная модель устройства, функционирующего в дискретном времени, которая перерабатывает конечную последовательность входных сигналов и превращает их в конечную последовательность выходных сигналов (реакций).
В процессе работы конечного автомата происходит последовательная смена конечного число его внутренних состояний, причем состояние автомата в определенный момент времени однозначно определяется входным и выходным сигналами. Такие автоматы представляют собой основу всей современной вычислительной техники и всевозможных дискретных систем автоматического контроля и управления.
Понятие автомата настолько абстрактное, что трудно сказать, когда человек вообще обходился без каких либо автоматов. Под определение автомата подходят любые устройства, в том числе те, которыми первобытные люди охотились или метали камни, защищая свое жилище от неприятеля.
Алгоритм – понятное и точное формальное предписание исполнителю, однозначно определяющее содержание и последовательность операций, переводящих заданную совокупность исходных данных в искомый результат
Считается, что первым программным устройством, созданным человеком, были часы. Часовые механизмы с помощью пружины, приводящей в действие шестеренки и кулачковые механизмы, зубчатые колеса и рычаги, осуществляют ряд определенных действий. Примером такого часового механизма могут быть знаменитые часы на Центральном театре кукол в Москве, где он приводит в действие двенадцать сказочных героев, расположенных на циферблате.
Укажем несколько любопытных исторических фактов, связанных с автоматами, как механическими устройствами.
1. Немецкий философ и алхимик Альберт Великий с 1216 по 1246 г., создавал «железного» слугу - автомат, который выполнял в доме обязанности привратника.
2. Астроном Иоганн Мюллер (Региамонтан) (1436-1476) создал механического орла, который приветствовал наклоном головы и движением крыльев въезд в Нюрнберг императора священной Римской империи Максимилиана II.
3. Механик Жак де Вакансон (1709-1782) – автор первого в мире автоматического ткацкого станка. Он создал образ механической утки, точной копии своего живого двойника - плавала, чистила перья, глотала с ладони зерна. Его механический флейтист, исполнявший одиннадцать музыкальных пьес, поражал людей, живших в те далекие годы.
4. Русский изобретатель 19 в. А. М. Гамулецкий создал целый механический кабинет, в котором было множество сконструированных им автоматов. Здесь в том числе была и говорящая голова чародея и амур, играющий на арфе, которые поражали воображение современников.
5. Первый примитивный арифмометр сконструировал в 1641 г. Блез Паскаль. Толчком для открытия были мучения его отца – налогового, инспектора, который днями и ночами работал с большими вычислениями. Изобретя арифмометр, восемнадцати летний сын избавил отца от сложных вычислений, а миру подарил первый калькулятор, производящий сложение и вычитание чисел.
6. Первый шахматный автомат был построен в 1890 г. испанским инженером Торресом Кеведо. Такой автомат мог разыграть лишь ладейный эндшпиль (король и ладья против короля).
7. Первую вычислительную машину с автоматическим управлением создал Чарльз Баббедж в 1822 г. Он спроектировал арифмометр , который имел запоминающие и арифметические устройства. Эти устройства стали прототипами аналогичных устройств современным ЭВМ.
Виды автоматов.
Автомат можно трактовать как устройство, выполняющие процессы приема, преобразования и передачи энергии, материалов или информации в соответствии с заложенной в них программой, но без непосредственного участия человека.
Любой автомат имеет собственные базовые множества, которые включают в себя:алфавит входа, алфавит выхода, множество состояний автомата.
Характерной особенностью конечного автомата является наличие памяти, которая определяет состояние автомата в зависимости от времени. Внешним проявлением различных состояний автомата является его реакция на однотипные воздействия (сигналы).
В работе конечных цифровых автоматов важным понятием является время.
Автоматы можно классифицировать по различным признакам.
1. По виду деятельности - автоматы делятся на: информационные, управляющие и вычислительные.
К информационным автоматам относятся разнообразные справочные таблицы, информационные табло на стадионах, устройства аварийной сигнализации.
К управляющим автоматам принято относить устройства для управления некоторым процессом, в том числе конкретно: лифтом, конвейером, станком, шлагбаумом.
К вычислительным автоматам относятся микрокалькуляторы, процессоры в ЭВМ и иные устройства, выполняющие вычисления.
Однако, строго говоря, многие, автоматы представляют собой настолько сложные системы, что они являются одновременно и вычислительными, и управляющими, и информационными автоматами.
2. Конечные автоматы – с точки зренияинформатики это такие автоматы, которые представляют собой дискретные преобразователи информации. К ним относятся преобразователи, в которых содержится конечное множество входных и конечное выходных сигналов, а также конечное множество внутренних состояний
3. Цифровые автоматы - автоматы, которые преобразует цифровую информацию. В таком автомате входные сигналы задаются в виде конечного множества мгновенных символов: их длительность настолько мала, что ею можно пренебречь. За фиксированное время происходит преобразование входных символов, а на выходе происходит скачкообразный переход из одного состояния в другое состояние.
4. Абстрактные автоматы - отображающие множество слов входного алфавита Х во множество слов выходного алфавита Y.
Абстрактный автомат есть:
~ Математическая модель,
~ Алгоритм действия некоторого преобразования кодовых последовательностей,
~ Закон преобразования входного алфавита в выходной.
5. Синхронные и асинхронные автоматы . В зависимости от того, одновременно или последовательно принимаются входной сигнал и сигнал смены состояний, автоматы делятся насинхронные и асинхронные автоматы.
В синхронных автоматах продолжительность входных сигналов и время переходов согласовано между собой. Они используются в вычислительных комплексах, АСУ и т.д.
В асинхронных автоматах продолжительность входных сигналов и время переходов не согласовано между собой. Они зависят от внешних источников - различных событий, а интервал дискретности является переменным (например, в кодовых замках). В асинхронных автоматах очередное изменение значений входных сигналов может произойти только при условии, что закончился переходный процесс, вызванный предыдущим изменением этих сигналов.
6. Автоматы делятся на конечные и бесконечные автоматы. Если в основании классификации лежит объем памяти, то различие заключается в том, имеет ли автомат конечное или бесконечное число внутренних состояний.
Под бесконечным автоматом обычно понимают определенную математическую идеализацию представлений об автомате, имеющую бесконечное число состояний. Память такого автомата потенциально может неограниченно возрастать. Например, известные абстрактные автоматы Поста и Тьюринга являются бесконечными автоматами, но сама ЭВМ или ее отдельные части - конечными автоматами.
7. Автоматы делятся на детерминированные и вероятностные автоматы . Если в основании классификации лежит механизм случайного выбора, то различают детерминированные и вероятностные (стохастические) автоматы.
В детерминированных автоматах поведение и структура в каждый момент времени однозначно определены текущей входной информацией и состоянием самого автомата в предшествующий момент времени.
В вероятностных автоматах эта зависимость связана еще и с некоторым случайным выбором.
Вероятностный автомат - это дискретный преобразователь информации, функционирование которого в каждый момент времени зависит только от состояний памяти и описывается статистическими законами.
8. Универсальный автомат. В теории автоматов доказано, что для выполнения различных преобразований информации достаточно построить универсальный автомат с помощью программы и соответствующего кодирования, способный решать любые задачи.
Математическая модель цифрового автомата с одним входом задается пятью объектами:
X- конечное множество входных символов, входной алфавит:
Х= {x 1 (t), x 2 (t), …, x n (t)};
Y- конечное множество выходных символов, выходной алфавит:
У={y 1 (t), y 2 (t), …, y n (t)};
Q ~ конечное множество состояний автомата:
Q= {q 0 (t), q 1 (t), q 2 (t), …, q n (t)}, q 0 - начальное состояние;
δ(q, х ) - функция перехода автомата из одного состояния в другое: (Q х X) ®Q;
λ(q, х ) ~ функция выхода автомата: (Q x Х) ® Y.
Таким образом, конечный автомат С= (X, Q, У, δ, λ.) определяется рекуррентными соотношениями
q(0) = q 0 , q(t + I) = δ (g(t), х(t)), y(t) = λ (g(t), х(t)),
t- дискретизированный момент времен или это есть образ монотонной функции t :. Т ® N, причем Т - обычное непрерывное время, N - множество натуральных чисел.
Все время работы Т разбивается на конечное число интервалов, на границе которых происходит изменение состояния автомата. При этом t(Г 0) – показывает число изменений, произошедших до момента времени Г 0 .
Примером дискретизации служит обычный кинематограф: время разбито на интервалы длительностью 1/24с. Человеческий глаз воспринимает следование дискретных кадров как непрерывное движение.
9. Синхронные автоматы делятся на автоматы Мили и автоматы Мура . В зависимости от способа организации функции выхода синхронные автоматы делятся на автоматы Мили (автоматы I рода) и автоматы Мура(автоматы II рода).
В автоматах Мили - выходной сигнал y (t) x (t) и состоянием q (t- 1) автомата в предшествующий момент времени (t- 1). Математической моделью таких автоматов служит система уравнений:
q(t) = δ (q(t-1), х(t)) и y(t) = λ (q(t-1), х(t)),
В автоматах Мура выходной сигнал y (t) однозначно определяется входным сигналом x (t) и состоянием q (t) в данный момент времени t. Математической моделью таких автоматов является система:
q(t) = δ (q(t-1), х(t)) и y(t) = λ (q(t)),
В таких автоматах функция выхода зависит только от состояний автомата в данный момент времени и не зависит от входного сигнала. Таким образом, входная строка такого автомата однократно считывается слева направо, осуществляя поочередный просмотр символов. В определенный момент времени конечный автомат находится в некотором внутреннем состоянии, которое изменяется после считывания очередного символа. Новое состояние можно охарактеризовать считанным символом и текущим состоянием.
10. Комбинационные автоматы – есть автоматы, в которых выходной символ не зависит от его состояния и определяется лишь текущими входными символами, т.е. в этом автомате все состояния эквивалентны. В таком автомате вырождена функция перехода, она принципиально не важна и в процессе функционирования неизменна. Поэтому минимальный комбинационный автомат имеет лишь одно состояние.
11 Логические автоматы – есть автоматы у которых входной алфавит состоит из 2 т двоичных наборов длины т, а выходной - из 2 n двоичных наборов длины п. Для логических комбинационных автоматов функция выхода имеет вид системы п логических функций от т переменных.