Математическая энциклопедия » Что такое «Автоматов Гомоморфизм»?

Значение слова, определение и толкование термина

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

Avtomatov Gomomorfizm

отображение входного и выходного алфавитов, а также множества состояний одного автомата в аналогичные множества другого автомата, сохраняющее функции переходов и выходов. Более точно А. г. автомата [Автоматов Гомоморфизм. Фото 1] в автомат [Автоматов Гомоморфизм. Фото 2] (см. Автомат конечный) - это отображение [Автоматов Гомоморфизм. Фото 3] множества [Автоматов Гомоморфизм. Фото 4] в множество [Автоматов Гомоморфизм. Фото 5] такое, что

[Автоматов Гомоморфизм. Фото 6]

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

[Автоматов Гомоморфизм. Фото 7]

Для автоматов инициальных, кроме того, требуется, чтобы функция hначальное состояние переводила в начальное. Автоматы [Автоматов Гомоморфизм. Фото 8] наз. гомоморфными, если существует А. г. Л, отображающий [Автоматов Гомоморфизм. Фото 9] на [Автоматов Гомоморфизм. Фото 10] Если, кроме того, отображение hвзаимно однозначно, то hназ. изоморфизмом, а автоматы [Автоматов Гомоморфизм. Фото 11] - изоморфными автоматами. Если алфавиты А 1 и А 2, а также В 1 и В 2 совпадают и отображения h1 и h3 тождественны, то гомоморфизм (изоморфизм) hназ. гомоморфизмом (изоморфизмом) по состояниям. Аналогично определяются гомоморфизмы (изоморфизмы) по входному и выходному алфавитам. Изоморфные по состояниям автоматы, а также гомоморфные по состояниям инициальные автоматы эквивалентны (см. Автоматов эквивалентность).

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

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

  • ВКонтакте

  • Facebook

  • Мой мир@mail.ru

  • Twitter

  • Одноклассники

  • Google+

См. также

  • НЬЮТОН        (Н, N), единица СИ силы. Названа в честь англ. учёного И. Ньютона (I. Newton). 1 Н — сила, сообщающая телу массой 1 кг ускорение 1 м/с2 в н

  • (от лат. stabilis-устойчивый), совокупность методов, применяемых для сохранения комплекса св-в полимеров и полимерных материалов в условиях их

  • углеводы, образованные остатками двух моносахаридов. В животных и растит. организмах распространены Д.: сахароза, лактоза, мальтоза, трегал