Чтобы задать конечный автомат S, необходимо описать все элементы множества: S={ X,A,Y,
,
,ao}. Существует несколько способов задания работы автомата, но наиболее часто используется табличный (матричный), графический, аналитический.
При табличном способе автомат задается двумя таблицами: таблицей переходов и таблицей выходов, или матрицей соединений. Таблица переходов произвольного полностью определенного автомата строится следующим образом: строки таблицы помечаются
буквами входного алфавита автомата, а столбцы таблицы - буквами алфавита состояний автомата; В клетке таблицы переходов, находящейся на пересечении строки, отмеченной входным сигналом xi, и столбца отмеченного состоянием aj, ставится состояние аk, являющееся результатом перехода автомата из состояния aj под воздействием входного сигнала хi, что определяется выражением ak= (aj, хj).
Таблица 1.1 Таблица переходов автомата
| Состояния | а1 | а2 | … | аk |
| входные сигналы | ||||
| x1 |
|
| . |
|
| … | ||||
| хj |
|
| … |
|
Пример заполнения таблицы переходов некоторого абстрактного полностью определенного автомата с входным алфавитом X={х1, х2} - и алфавитом состояний A={a1, a2, а3} представлен в табл.1.2.
Таблица 1.2
| А | а1 | a2 | а3 |
| х | |||
| х1 | а2 | а3 | а1 |
| x2 | а1 | а1 | a2 |
Если абстрактный автомат частичный, то в клетке таблицы его переходов, находящейся, на пересечении строки, отмеченной входным сигналом и столбца отмеченного соответствующим состоянием (при условии, что переход в это состояние под действием данного входного сигнала не определен) ставится прочерк, и любое входное слово, приводящее к указанному переходу является запрещенным.
Заполнение остальных клеток аналогично случаю полностью определенного автомата. Вид таблицы переходов не зависит от типа задаваемого автомата (автомат Мили, Мура, С-автомат). Таблицы выходов автоматов Мили, Мура, С-автомата имеют различия.
Таблица выходов полностью определенного автомата Мили строится следующим образом: идентификация столбцов и строк, а также формат таблицы соответствуют таблице переходов полностью определенного автомата. В клетке таблицы выходов, находящейся на пересечении строки, отмеченной входным сигналом Xj, и столбца, отмеченного состоянием ак, ставится выходной сигнал Уm, который автомат выдает, находясь в состоянии аk при наличии входного сигнала Xj, что определяется выражением Ym= (аk, хj).
Таблица 1.3 Таблица выходов абстрактного автомата Мили.
| Состояния | a1 | a2 | ak | |
| Входные сигналы | ||||
| х1 |
|
|
| |
| … | …. | . | ||
| хj |
|
|
|
Другое по теме:
Синтез системы автоматического регулирования фокусировки пятна В настоящее время оптические дисковые системы нашли множество применений. Возможность записи значительного объема информации и простота тиражирования делает оптический диск очень привлекательным. В сфере записи и хранения данных системы с прямой ...