Автоматов гомоморфизм

отображение входного и выходного алфавитов, а также множества состояний одного автомата в аналогичные множества другого автомата, сохраняющее функции переходов и выходов. Более точно А. г. автомата [img: http://localhost:8080/file/010106-103.jpg] в автомат [img: http://localhost:8080/file/010106-104.jpg] (см. Автомат конечный) - это отображение [img: http://localhost:8080/file/010106-105.jpg] множества [img: http://localhost:8080/file/010106-106.jpg] в множество [img: http://localhost:8080/file/010106-107.jpg] такое, что [img: http://localhost:8080/file/010106-108.jpg] и для любых s из S1 и аиз А 1 имеют место равенства: [img: http://localhost:8080/file/010106-109.jpg] Для автоматов инициальных, кроме того, требуется, чтобы функция hначальное состояние переводила в начальное. Автоматы [img: http://localhost:8080/file/010106-110.jpg] наз. гомоморфными, если существует А. г. Л, отображающий [img: http://localhost:8080/file/010106-111.jpg] на [img: http://localhost:8080/file/010106-112.jpg] Если, кроме того, отображение hвзаимно однозначно, то hназ. изоморфизмом, а автоматы [img: http://localhost:8080/file/010106-113.jpg] - изоморфными автоматами. Если алфавиты А 1 и А 2, а также В 1 и В 2 совпадают и отображения h1 и h3 тождественны, то гомоморфизм (изоморфизм) hназ. гомоморфизмом (изоморфизмом) по состояниям. Аналогично определяются гомоморфизмы (изоморфизмы) по входному и выходному алфавитам. Изоморфные по состояниям автоматы, а также гомоморфные по состояниям инициальные автоматы эквивалентны (см. Автоматов эквивалентность). Понятие А. г. используется в связи с задачами минимизации, разложения, полноты автоматов и др.