Понятие дискретного автомата

Общие подходы к описанию устройств.

АВТОМАТЫ

ЛЕКЦИЯ № 4

Основные вопросы:

ü Общие подходы к описанию устройств

ü Конечные автоматы

ü Автоматы без памяти

ü Автоматы с бесконечной памятью

В технике термином «автомат» пользуются для обозначения системы механизмов и устройств, в которой процессы получения преобразования, передачи и использования энергии, материалов и информации, необходимые для выполнения ее функций, осуществляют­ся без непосредственного участия человека. К системам такого ти­па относятся: станки-автоматы, фасовочные автоматы, автоматы для съемки и изготовления фотографий, торговые автоматы и многое др.

В кибернетику, однако, вошел и прочно в ней укрепился термин «дискретный автомат» или кратко просто «автомат» для обозначения гораздо более абстрактного понятия, а именно - модели, обладаю­щей следующими особенностями:

а) на входы модели в каждый из дискретных моментов времени t₁, t₂,… поступают m входных величин x₁,x₂,…x­_m. каждая из которых может принимать конечное число фиксированных значений из входного алфавита Х;

б) на выходах модели можно наблюдать n выходных величин y₁,…y_n каждая из которых может принимать конечное число фиксированных значений из выходного алфавита Y;

в) в каждый момент времени модель может находиться в одном из состояний z₁,z₂,…z_n;

г) состояние модели в каждый момент времени определяется входной величиной x в этот момент и состоянием z в предыдущий момент времени;

д) модель осуществляет преобразование ситуации на входе x={x₁,x₂,…,x_m} в ситуацию на выходе y={y₁,y₂,…,y_n} за­висимости от ее состояния в предыдущий момент времени.

Рис. 1 Дискретный автомат

Такая модель (рис.1) удобна для описания многих ки­бернетических систем.

Автоматы, у которых ситуация y на выходах однозначно определяется ситуацией х на входах, мы будем относить к классу автоматов без памяти. Автоматы, у которых у зависит не только от значения х в данный момент, но и от состояния модели z, определяемого значениями х в предыдущие моменты времени, относятся к классу автоматов с конечной памятью.

Мы ограничимся рассмотрением лишь простейших из дискретных автоматов, входной и выходной алфавиты которых состоят всего из двух букв: 0 и 1. Это оправдывается тем что, как оказывается в теории автоматов, автоматы с такими "бедными" алфавитами способ­ны решать такие же задачи, как и автоматы с любыми другими алфа­витами.

Теория дискретных автоматов приобрела большое значение для решения некоторых фундаментальных проблем информатики, которые связаны с принципиальными возможностями переработки информации в ИС.