Спирина, М.С. Дискретная математика

Рис. 7.2. Схема работы кодового замка если никто не пытается взломать замок, автомат продолжает ра­ ботать — подается сигнал *. Рассмотренный кодовый замок будет являться асинхронным ав ­ томатом. Действительно, как известно из определения, у асин­ хронных автоматов время действия входного сигнала не совпадает со временем смены состояний, а следующий входной сигнал авто­ мат получает после перехода в новое состояние. Для того чтобы неопределенное время действия входного сигнала не отражалось на работе такого автомата, после получения повторного сигнала он не меняет своего состояния. Так, при повторном нажатии кнопки В автомат остается в состоянии q2, а при повторной паузе * — в q2. Описанный процесс называют этапом абстрактного синтеза автоматов или этапом синтеза абстрактных автоматов. Итак, абстрактный автомат есть математическая модель, алго­ ритм действия некоторого преобразования кодовых последователь­ ностей, закон преобразования входного алфавита в выходной. 7.3. Общие задачи теории автоматов Sapienti sat — для понимающего достаточно. Плавт Абстрактный автомат рассматривается только как преобразо­ вание входных последовательностей в выходные, без учета его структуры. Но не всякое преобразование последовательностей может быть представлено конечным автоматом. Одной из главных проблем абстрактной теории автоматов является выяснение того, какие возможны преобразования, как их описать и каким обра­ зом математическая сущность этих преобразований связана с чис­ лом состояний, а значит, и со степенью сложности автоматов. Принято выделять три основные задачи теории автоматов. Задача синтеза заключается в том, что необходимо построить автомат Z, реализующий отображение множества слов над алфа­ витом X во множество слов над алфавитом Y. 351