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

К информационным автоматам мы относим разнообразные спра­ вочные таблицы, например, на вокзалах, информационные таб­ ло на стадионах, различные устройства аварийной сигнализации. К управляющим автоматам принято относить устройства для уп­ равления лифтом, конвейером, различные типы управляемых стан­ ков, автоматические шлагбаумы. К вычислительным автоматам мы будем относить микрокалькуляторы (МК) и процессоры в ЭВМ. Однако, строго говоря, эти сложные системы являются одновре­ менно и вычислительными, и управляющими, и информацион­ ными. В информатике конечным автоматом называют дискретный пре­ образователь информации, т.е. преобразователь, в котором мно­ жество входных и выходных сигналов, а также множество внут­ ренних состояний являются конечными множествами. Автомат называют цифровым, если он преобразует цифровую информацию. В таком автомате входные сигналы задаются в виде конечного множества мгновенных символов: их длительность на­ столько мала, что ею можно пренебречь. За фиксированное время t происходит преобразование входных символов, а на выходе про­ исходит скачкообразный переход из состояния q, (t) в состояние 0*1 ( 0 (рис. 7.1). Таким образом, абстрактный автомат отображает множество слов входного алфавита X во множество слов выходного алфави­ та Y. Входной и выходной алфавиты, а также множество состоя­ ний автомата называют его базовыми множествами. Характерной особенностью конечного автомата является на­ личие памяти, которая определяет состояние автомата в зависи­ мости от времени. Внешним проявлением различных состояний автомата является его реакция на однотипные воздействия (сиг­ налы). В работе конечных цифровых автоматов важное значение имеет время. В зависимости от того, одновременно или последовательно принимаются входной сигнал и сигнал смены состояний, авто­ маты делятся на синхронные и асинхронные. В синхронных автоматах продолжительность входных сигналов и время переходов согласованы. Они используются, например, в вычислительных комплексах, АСУ и т.д. В асинхронных автоматах продолжительность входных сигна­ лов и время переходов не согласованы. Они зависят от внешних источников — различных событий, а интервал дискретности яв­ ляется переменным (например, в кодовых зам­ ках). В асинхронных автоматах очередное измене­ ние значений входных сигналов может произойти только при условии, что закончился переходный Рис. 7.1. Схема процесс, вызванный предыдущим изменением этих автомата сигналов. Щ Пд 344