АВТОМАТОВ ГОМОМОРФИЗМ это:

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

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


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


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

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

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


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "АВТОМАТОВ ГОМОМОРФИЗМ" в других словарях:

  • АВТОМАТОВ АЛГЕБРАИЧЕСКАЯ ТЕОРИЯ — направление в автоматов теории, характеризующееся использованием алгебраич. средств в изучении автоматов. А. а. т. основана на том, что автоматы можно рассматривать как нек рые специальные алгебры или алгебраические системы. Кроме того, события,… …   Математическая энциклопедия

  • СЕМИОТИКА — (от греч. semeiot знак) общая теория знаковых систем, изучающая свойства знаковых комплексов самой различной природы. К таким системам относятся естественные языки, письменные и устные, разнообразные искусственные языки, начиная с формализованных …   Философская энциклопедия

  • АЛГЕБРА — часть математики, посвященная изучению алгебраических операций. Исторический очерк. Простейшие алгебраич. операции арифметич. действия над натуральными и положительными рациональными числами встречаются в самых ранних математич. текстах,… …   Математическая энциклопедия

  • Полугруппа —         одно из основных понятий современной алгебры. П. называется множество с определённой на нём операцией, подчинённой закону ассоциативности (См. Ассоциативность). Понятие П. есть обобщение понятия группы (См. Группа): из аксиом группы… …   Большая советская энциклопедия

  • ПРЕДСТАВЛЕНИЕ ПОЛУГРУППЫ — S в классе полугрупп X гомоморфизм полугруппы S в нек рую полугруппу из класса X (в случае изоморфизма говорят о точном представлении). Обычно имеются в виду классы каких либо конкретных полугрупп. Наиболее изучены представления в классе… …   Математическая энциклопедия

  • МНОГОЗНАЧНЫЕ ЛОГИКИ —     МНОГОЗНАЧНЫЕ ЛОГИКИ обобщение классической двузначной логики (см. Логика высказываний) к примеру, посредством которого к обычным истинностным значениям “истина” и “ложь” добавляются и другие (промежуточные) значения. Этот факт указывает на то …   Философская энциклопедия

  • МНОГОЗНАЧНЫЕ ЛОГИКИ – — обобщение классической двузначной логики (см. Логика высказываний) к примеру, посредством которого к обычным истинностным значениям «истина» и «ложь» добавляются и другие (промежуточные) значения. Этот факт указывает на то, что принцип… …   Философская энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»