АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Т а б л и ц а 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).


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |


Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)