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

Расстановка ударений: АВТОМА`ТОВ ГОМОМОРФИ`ЗМ

АВТОМАТОВ ГОМОМОРФИЗМ - отображение входного и выходного алфавитов, а также множества состояний одного автомата в аналогичные множества другого автомата, сохраняющее функции переходов и выходов. Более точно А. г. автомата ₁ = (A₁, S₁, В₁, φ₁, ψ₁) в автомат ₂ = (A₂, S₂, В₂, φ₂, ψ₂) (см. Автомат конечный) - это отображение h = (h₁, h₂, h₃) множества A₁ × S₁ × B₁ в множество A₂ × S₂ × B₂ такое, что

h₁ : A₁ → A₂, h₂ : S₁ → S₂, h₃ : B₁ → B₂,

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

h₂ φ₁ (s, a) = φ₂ (h₂ (s), h₁ (a)), h₃ ψ₁ (s, a) = ψ₂ (h₂ (s), h₁ (a)).

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

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

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

А. А. Летичевский.

Источники:

1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.