On the frame of an automaton.pdf В [1] было введено понятие каркаса автомата. Это упорядоченное множество, котороеобразуют слои автомата вместе с отношением обратной достижимости. Оно сыграловесьма существенную роль в описании автоматов, у которых каждая конгруэнцияявляется ядром подходящего эндоморфизма. В работе устанавливаются некоторыесвойства каркаса, связанные с основными алгебраическими конструкциями дляавтоматов, такими, как подавтомат, гомоморфизм, конгруэнция.Автомат - это тройка A = (S, X , 8), где S и X - конечные непустые множества,соответственно множество состояний и множество входных сигналов, а 8 : S x X ^ S -отображение, называемое функцией переходов.Подмножество S' С S называется устойчивым в автомате A, если 8(s,x) E S' длялюбых s E S' и x E X . Если S' устойчиво в A, то, ограничивая функцию переходов 8на S' x X , получают автомат A' = (S ',X , 8) -подавтомат автомата A, соответствующийS'. Совокупность SubA всех подавтоматов автомата A, упорядоченная отношениемA i ^ A 2 S1 С S2, где Ai = (Sj,X, 8), i = 1, 2, является дистрибутивнойрешеткой.Пусть A = (S, X , 8) и B = (T, X, 8) - сравнимые автоматы, т. е. автоматы с одним итем же множеством входных сигналов. Отображение ^ : S ^ T по определению являетсягомоморфизмом автомата A в автомат B, если

Скачать электронную версию публикации