Математическая энциклопедия - автоматов гомоморфизм
Связанные словари
Автоматов гомоморфизм
отображение входного и выходного алфавитов, а также множества состояний одного автомата в аналогичные множества другого автомата, сохраняющее функции переходов и выходов. Более точно А. г. автомата в автомат (см. Автомат конечный) - это отображение множества в множество такое, что
и для любых s из S1 и аиз А 1 имеют место равенства:
Для автоматов инициальных, кроме того, требуется, чтобы функция hначальное состояние переводила в начальное. Автоматы наз. гомоморфными, если существует А. г. Л, отображающий на Если, кроме того, отображение hвзаимно однозначно, то hназ. изоморфизмом, а автоматы изоморфными автоматами. Если алфавиты А 1 и А 2, а также В 1 и В 2 совпадают и отображения h1 и h3 тождественны, то гомоморфизм (изоморфизм) hназ. гомоморфизмом (изоморфизмом) по состояниям. Аналогично определяются гомоморфизмы (изоморфизмы) по входному и выходному алфавитам. Изоморфные по состояниям автоматы, а также гомоморфные по состояниям инициальные автоматы эквивалентны (см. Автоматов эквивалентность).
Понятие А. г. используется в связи с задачами минимизации, разложения, полноты автоматов и др.
Лит.:[1] Глушков В. М., "Успехи матем. наук", 1961, т. 16, в. 5, с. 3-62. Л. Л. Летичевский.
Математическая энциклопедия. — М.: Советская энциклопедия
И. М. Виноградов
1977—1985
Вопрос-ответ:
Похожие слова
Самые популярные термины
1 | 548 | |
2 | 475 | |
3 | 471 | |
4 | 464 | |
5 | 448 | |
6 | 432 | |
7 | 430 | |
8 | 425 | |
9 | 417 | |
10 | 416 | |
11 | 415 | |
12 | 405 | |
13 | 397 | |
14 | 371 | |
15 | 368 | |
16 | 362 | |
17 | 357 | |
18 | 356 | |
19 | 356 | |
20 | 355 |