АВТОМАТОВ ГОМОМОРФИЗМ

отображение входного и выходного алфавитов, а также множества состояний одного автомата в аналогичные множества другого автомата, сохраняющее функции переходов и выходов. Более точно А. г. автомата в автомат (см. Автомат конечный) - это отображение множества в множество такое, что

и для любых s из S₁ и аиз А ₁ имеют место равенства:

Для автоматов инициальных, кроме того, требуется, чтобы функция hначальное состояние переводила в начальное. Автоматы наз. гомоморфными, если существует А. г. Л, отображающий на Если, кроме того, отображение hвзаимно однозначно, то hназ. изоморфизмом, а автоматы - изоморфными автоматами. Если алфавиты А ₁ и А _2, а также В ₁ и В ₂ совпадают и отображения h₁ и h₃ тождественны, то гомоморфизм (изоморфизм) hназ. гомоморфизмом (изоморфизмом) по состояниям. Аналогично определяются гомоморфизмы (изоморфизмы) по входному и выходному алфавитам. Изоморфные по состояниям автоматы, а также гомоморфные по состояниям инициальные автоматы эквивалентны (см. Автоматов эквивалентность).

Понятие А. г. используется в связи с задачами минимизации, разложения, полноты автоматов и др.

Лит.:[1] Глушков В. М., "Успехи матем. наук", 1961, т. 16, в. 5, с. 3-62. Л. Л. Летичевский.