Cтраница 3
Несложно проверить, что это действительно биавтомат. [31]
Класс всех коавтоматов, рассматриваемых как биавтоматы, также является многообразием биавтоматов. Кортеж тождеств многообразия совпадает с кортежем его свободного биавтомата. [32]
Аналогично определяется треугольное произведение автоматов и биавтоматов. [33]
Пусть Xv и Х2 - многообразия биавтоматов; их произведение Х Х2 определяется следующим образом: биавтомат А ( А, Г, В) принадлежит XtX2 тогда и только тогда, когда найдется такой подавтомат А ( А1, Г, В), лежащий в Xlt что AIAi ( A / AY, Г, В / В1) принадлежит Хг. Так, определенное произведение многообразий ассоциативно. [34]
Непосредственно проверяется, что в результате получим биавтомат, который называется биавтоматом Мура. Понятно, что если f / перестановочно с действием Г, то соответствующая операция оказывается нулевой. [35]
Класс всех линейных автоматов, рассматриваемых как биавтоматы, образует многообразие биавтоматов. [36]
Гомоморфизмы по состояниям не сохраняют муровское свойство биавтоматов. [37]
В частности, кортеж Г - тождеств биавтомата ( или класса биавтоматов) является согласованным. [38]
AT; в нем действие станет нулевым и универсальный биавтомат Atm3 ( A, Г) превратится в соответствующий универсальный линейный автомат. [39]
Таким образом, между системами Г - тождеств биавтоматов и Г - вполне характеристическими подавтоматами вида ( Olt Г, Т) свободного биавтомата существует взаимно однозначное соответствие. [40]
Биавтомат А называется делителем биавтомата В, если уточнение биавтомата А является эпимоморфным образом подавтомата из В. Под декомпозицией биавтомата понимается представление его в виде делителя некоторой конструкции из других биав-томатов - компонент декомпозиции. В данном случае в качестве конструкции берется треугольное произведение и требуется, чтобы компоненты декомпозиции являлись делителями исходного биавтомата. Сейчас будет доказана теорема о возможности вложения биавтомата в треугольное произведение своего подавтомата и фактор-автомата по нему. Итерируя процесс вложения, мы придем затем к такой декомпозиции, компоненты которой являются простыми биавтоматами. [41]
Еще одним обобщением понятия полугруппового линейного автомата является понятие биавтомата. Речь идет о такой ситуации, когда входные сигналы воздействуют не только на состояния автомата, но и на его выходы. [42]
Будем обозначать свободные линейные Г - автомат и Г - биавтомат соответственно Atmr ( Z. Там, где понятно, о чем идет речь, индексы / и Ь можно опускать. [43]
Пусть А ( А, Г, В) - произвольный биавтомат, a ij /: А - В - линейное отображение. [44]
Для сравнения полезно заметить: в связи с тем что первый универсальный биавтомат Aim ( А, В) ( А. [45]