Определение 4: Морфизмом называется такое отображение , что и и . Если сюрьективно, то морфизм называется эпиморфизмом. Если - биекция, то морфизм называется изоморфизмом.
Теорема 2: Пусть эпиморфизм автомата
на
. Тогда для любой входной строки
и любого начального состояния
входная строка
автомата
совпадает с входной строкой автомата
, если начальное состояние
равно
.
Доказательство:Доказательство можно провести индукцией по числу с индуктивным шагом:
;
.
Следствие: Любой эпиморфизм определяет покрытие автомата
автоматом
. Изоморфизм автоматов
и
с общим входным и выходным алфавитами есть биекция
, такая, что для всякого начального состояния
и всякой входной строки
автоматы
и
выдают одну и ту же выходную строку, проходя через соответствующие промежуточные состояния.
Пример. Автоматы, представленные следующими ориентированными графами, изоморфны.