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

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

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

а) на входы модели в каждый из дискретных моментов времени 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. Это оправдывается тем что, как оказывается в теории автоматов, автоматы с такими "бедными" алфавитами способ­ны решать такие же задачи, как и автоматы с любыми другими алфа­витами.

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

Минимизация абстрактного автомата

Автомат с большим числом различных состояний реализуется сложнее, чем автомат с меньшим числом состояний. Поэтому на этапе абстрактного синтеза можно поставить задачу отыскания автомата с минимально возможным числом состояний, реализующего исходное задание. Такая задача называется минимизацией числа состояний автомата, Для её решения введем понятие об эквивалентности состояний автомата и об эквивалентности автомата.

Обозначим A/ai - автомат А в состоянии аi Состояние ai автомата A1 эквивалентно состоянию aj автомата А2, если A1/ai и A2/aj под воздействием любой последовательности входных сигналов вырабатывают одинаковые выходные последовательности. Состояния ai и aj могут принадлежать одному автомату (т.е. A1 =А2).

Два автомата A1 и А2 эквивалентны, если каждому состоянию ai автомата A1 эквивалентно по крайней мере одно состояние автомата А2 и если при этом каждому состоянию aj автомата A1 эквивалентно по крайней мере одно состояние автомата А\. Группа эквивалентных состояний автомата может заменяться одни состоянием. Таким образом задача минимизации числа состояний автомата сводится к отысканию автомата, эквивалентного заданному, с минимально возможным числом состояний.

Задан автомат А из класса автоматов, эквивалентных автомату А, требуется выбрать A_mi_n с минимальным числом внутренних состояний. Существование для любого А эквивалентно A_mi_n с минимальным числом внутренних состояний впервые было доказано Муром.

Рассмотрим алгоритм минимизации, предложенных Ауфен-Каммом и Хоном, для полностью определенных автоматов Мили.

Все состояния исходных автоматов разбиваются на попарно не пересекающиеся группы эквивалентных состояний, затем каждая группа эквивалентных состояний замещается одним состоянием. Получающийся минимальный автомат имеет столько же состояний, на сколько групп эквивалентных состояний разбиваются состояния исходного автомата. Процесс разбиения состояний на группы эквивалентных состояний является многошаговым.

Два состояния автоматов называются одноэквивалентными, если автомат, находясь в любом из этих двух состояний, при подаче одинаковых входных сигналов вырабатывает одинаковые выходные сигналы. Объединение всех одно эквивалентных состояний автоматов образует 1 класс эквивалентности.

Индуктивно можно распространить определение до i эквивалентных состояний i-o класса эквивалентности.

Если для каждого i класс эквивалентности i совпадает с (i+l)-ым классом, то он совпадает и со всеми последующими до конечного класса и называется бесконечным или финальным классом эквивалентности. Финальный класс эквивалентности можно получить за конечное число шагов.

Пример: задан граф полностью определенный автоматом Мили (рис.2.).

Разбиение на группы одноэквивалентных состояний выглядит так: {ао}, {а1,а4}, {а₂,аз}.

Действительно, если автомат находится в состоянии a1 либо а4, то при подаче хо и x1 автомат вырабатывает одинаковые выходные сигналы уо и уо. Если автомат находится в состоянии а2 или аз, при подаче хо и X1 вырабатываются такие одинаковые сигналы y1 и уо.

Состояние ао нельзя включить ни в одну из этих групп двух эквивалентных состояний. Из состояний a1 и а4 при подаче хо автомат переходит в одно и то же состояние ао, а при подаче x1 - в состояния а₂ и а₃, которые принадлежат одной группе 1 класса эквивалентности. Из состояний а₂ и а3 при подаче хо автомат переходит в состояние a1 и а4, при подаче x1 - в состояние а₂ и а₃, но пары {а1,а4} и {а₂, а₃} являются одноэквивалентными, следовательно, 2 класс эквивалентности совпадает с 1 классом эквивалентности, а следовательно, последним является финальным классом.

Обозначим каждую группу финального класса через новое состояние: {а₀} - b₀, {а1 а₄ }-b1, {а₂, а₃}-b₂.

Таблица переходов эквивалентного минимального автомата представим в таблице 2, а заданный минимальный автомат изобразим на рис.18.

Группы эквивалентности можно получить с помощью треугольной таблицы, которая строится следующим образом: строки обозначаются состояниями а1, а₂, аз,.., аh-1, а столбцы а1, а₂, аз,.., аh-₂, где h - число состояний автомата.

На пересечении i-ой строки и j-гo столбца записываются условия, при которых возможно объединение состояний ai и aj. Если состояния нельзя объединить не при каких условиях, ставится знак *, если объединяются безусловно, то знак v.

Клетки соответствующими пересечениями строк и столбцов с одинаковыми индексами, не дополняются. Окончательное объединение состояний определяется на основании анализа непротиворечивости условий (см. таблицу 2.).

Как видно из таблицы, состояния a1 и а₄ можно объединить при условии объединений состояний а₂ и а3 в одну группу, а состояния а₂ и а3 объединяются при условии объединения состояния a1 и а₄ в одну группу, а также при объединении а₂ и а3. Это условие не является противоречивым, поэтому объединяются пары a1 и а₄, а также а₂ и аз.

При минимизации автомата Мура вводится понятие нуль эквивалентных состояний и О класса эквивалентности. Нуль-эквивалентными называются любые одинаково отмеченные состояния автоматов Мура. Если два нуль-эквивалентных состояния любым входным сигналом переводятся в два нуль-эквивалентных состояния, то они называются одноэквивалентными. Все дальнейшие классы эквивалентности состояний для автомата Мура определяются аналогично приведенному выше для автомата Мили.

Пример: задан автомат Мура отмеченный таблицей переходов (таблица 3).

Разбиение на классы эквивалентных выглядят так: {ао,a₂,а₄} и {а1,а₃} - 0 класс; {а₀,а₂,а₄}, {a1} и {а₃} - 1 класс;

{ао,а₂,а₄}, {a1} и {а3} - 2 класс, а следовательно и финальный класс эквивалентны.

Обозначив каждую группу финального класса эквивалентности новым состоянием, соответственно bo, b₂, b₄, построим облегченную таблицу переходов эквивалентного минимального автомата ядра (таблица 4).

Треугольная таблица для автомата Мура строится аналогично таблицы для автомата Мили и выглядит для рассматриваемого примера следующим образом:

Таблица заполняется так: ставится знак * в клетках, соответствующих номерам состояний с разными выходными сигналами. Затем в оставшихся клетках записываются условия, при которых эти состояния могут быть объединены и проверяется возможность выполнения этих условий. Если условия не выполнимы, в клетке ставится *.

На основании анализа непротиворечивости условий состояния объединяются в группы эквивалентности. Из таблицы 4 видно, что a1 и а3 можно объединить в одну группу эквивалентностей при условии объединения a1 и а₃, а также а1 и а₂. Первое условие тривиально, а второе невыполнимо, так как на пересечении а1 и а₂ стоит знак *.

Не нашли, что искали? Воспользуйтесь поиском: