Определение 4: Морфизмом называется такое отображение , что и и . Если сюрьективно, то морфизм называется эпиморфизмом. Если - биекция, то морфизм называется изоморфизмом

Теорема 2: Пусть эпиморфизм автомата на . Тогда для любой входной строки и любого начального состояния входная строка автомата совпадает с входной строкой автомата , если начальное состояние равно .

Доказательство: Доказательство можно провести индукцией по числу с индуктивным шагом:

;

.

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

Пример. Автоматы, представленные следующими ориентированными графами, изоморфны.

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