 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Т а б л и ц а 2.4
Отмеченная таблица переходов автомата Мура с пятью состояниями (z0, z1, z2, z3, z4), двумя входными (x1, x2) и тремя выходными (y1, y2, y3) сигналами
| Входы xi | Состояния zk | ||||
| y1 | y1 | y3 | y2 | y3 | |
| z0 | z1 | z2 | z3 | z4 | |
| x1 | z1 | z4 | z4 | z2 | z2 |
| x2 | z3 | z1 | z1 | z0 | z0 |
Для автоматов Мили эта разметка производится так: если входной сигнал xk действует на состояние zi, то, согласно сказанному, получается дуга, исходящая из zi и помеченная xk; эту дугу дополнительно отмечают выходным сигналом y = ψ (zi, xk). На рис. 2.3 приведён заданный ранее таблицей 2.2 граф F –автомата Мили.
Рис. 2.3. Граф автомата Мили
Для автоматов Мура аналогичная разметка графа такова: если входной сигнал xk, действуя на некоторое состояние zi автомата, вызывает переход в состояние zj, то дугу, направленную в zj и помеченную xk, дополнительно отмечают выходным сигналом y = ψ (zj, xk). На рис. 2.4 приведён заданный ранее таблицей 2.4 граф F –автомата Мура.
Рис. 2.4. Граф автомата Мура
Матричный способ задания конечного автомата часто является более удобной формой. При этом матрица соединений автомата есть квадратная матрица C = [ cij ], строки которой соответствуют исходным состояниям, а столбцы – состояниям перехода.
В случае F –автомата Мили элемент cij = xk / ys, стоящий на пересечении i -ой строки и j -го столбца, соответствует входному сигналу xk, вызвавшему переход из состояния zi в состояние zj, и выходному сигналу ys, выдаваемому при этом переходе. Для автомата Мили, рассмотренного выше, матрица соединений имеет вид
. (2.9)
Если переход из состояния zi в состояние zj происходит под действием нескольких сигналов, элемент матрицы cij представляет собой множество пар «вход-выход» для этого перехода, соединённых знаком дизъюнкции.
Для F –автомата Мура элемент cij = xk / ys равен множеству входных сигналов на переходе (zi, zj), а выход описывается вектором выходов, i -я компонента которого – выходной сигнал, отмечающий состояние zi. Для автомата Мура, рассмотренного выше, матрица соединений и вектор выходов имеют вид
; 
. (2.10)
Для детерминированных автоматов выполняется условие однозначности переходов: автомат, находящийся в некотором состоянии, под действием любого входного сигнала не может перейти более чем в одно состояние. Это означает, что в графе автомата из любой вершины не могут выходить две и более дуг, отмеченных одним и тем же входным сигналом, а в матрице соединений в каждой строке входной сигнал не должен встречаться более одного раза.
Рассмотрим таблицу переходов и граф асинхронного конечного автомата. Для F –автомата состояние zk называется устойчивым, если для любого входа xi Î X, для которого φ (zk, xi) = zk имеет место ψ (zk, xi) = yk. Таким образом, F –автомат называется асинхронным, если каждое его состояние zk Î Z устойчиво.
Ниже приведён пример асинхронного автомата Мура, заданного таблично (табл.2.5) и графически (рис.2.5).
Поиск по сайту: