Морфизмы

Покрытие и эквивалентность.

Пусть - конечный автомат. Тогда по любой входной строке длины r и по любому начальному состоянию однозначно определяется строка длины r внутренних состояний , которая получается последовательным применением отображения . Точнее: . Аналогично строка на выходе определяется последовательным применением отображения . Поэтому рассмотрим автомат как устройство, перерабатывающее пары, состоящие из состояния и в строки и . С помощью функций и можно определить функции , , которые строятся по функциям и , заданным в описании автомата М.

Пример. Автомат задан диаграммой:

Пусть входная строка и начальное состояние , тогда _, .

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

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

Определение 1: Говорят, что автомат покрывает автомат , если входной и выходной алфавиты у них общие и существует функция , такая что для любого положительного числа имеет место условие:

.

Определение 2: Автомат, который нельзя покрыть меньшим автоматом, называется минимальным. Будем писать: , если покрывает .

Теорема 1: Отношение покрытий рефлексивно и транзитивно.

Доказательство очевидно.

Определение 3: Автоматы и называются эквивалентными, если автомат покрывает и автомат покрывает . В этом случае пишут: .

Это означает, что кроме функции со свойством, указанным в предыдущем определении, существует еще функция со следующим свойством: при и .

Следствие: Отношение эквивалентности автоматов рефлексивно, транзитивно и симметрично.

Пусть и – автоматы с общими входными и выходными алфавитами.

Дата добавления: 2014-01-03