Эквивалентные автоматы

Автоматы являются устройствами для переработки дискретной информации. При этом характером перерабатываемой информации определяется входной и выходной алфавиты (X и Y); алфавит внутренних состояний (Q) определяется строением автомата и, вообще говоря, он может различаться у разных автоматов с одинаковыми входными и выходными алфавитами. Следовательно, одно и то же преобразование информации может быть осуществлено автоматами с разным числом состояний и, следовательно, посредством различного числа команд. Введем ряд определений:

Состояния q автомата М и q' автомата М' считаются эквивалентными,если оба автомата, получив одну и ту же (любую) входную последовательность символов, перерабатывают ее в одинаковую выходную последовательность.

Автоматы М и М' называются эквивалентными,если для каждого состояния автомата М существует эквивалентное ему состояние автомата М' и наоборот.

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

Понятие эквивалентности состояний применимо и к одному автомату (формально можно считать, что М и М' совпадают). Для одного автомата эквивалентными будут различные состояния, через которые одна и та же входная последовательность символов преобразуется в одинаковую выходную.

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

Автомат, эквивалентный заданному и имеющий наименьшее из всех возможных число состояний называется минимальным.

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

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

Контрольные вопросы и задания

Глава 4. Представление и обработка чисел в компьютере

Пример А.5

Классификация способов представления алгоритмов

Исполнитель алгоритма

Вернуться в оглавление: Теоретические основы информатики