Автор: О.М. Копытова
Источник: Материалы ХІ международной научно-практической конференции Математическое и программное обеспечение интеллектуальных систем (MPZIS-2013). Днепропетровск, 20-22 ноября 2013. – С. 119-120.
В работе продолжается изучение автоматов, устойчивых по поведению к локальной операции – переброске дуг. Под автоматом понимается приведенный автомат Мили A = (S,Х,Y,δ,λ), где S, Х, Y – множества состояний, входных и выходных символов соответственно, а δ, λ – функции переходов и выходов. Если Х={x}, т.е. x – единственный входной символ, то автомат называется автономным. Пусть е=(s,x′,y′,s1) – дуга в графе переходов автомата А. Переброской дуги е в состояние s2, отличное от s1, называем замену этой дуги на дугу (s, x′, y′, s2). Пусть автомат А′ получен из автомата А переброской некоторого множества его дуг. Если при этом автомат А′ остается изоморфным исходному автомату A, то говорим, что переброска сохраняет изоморфизм. Задача заключается в том, чтобы исследовать структуру циклов в автомате и найти условия, при которых существуют переброски, сохраняющие изоморфизм.
В доказано, что переброска одной дуги в любом приведенном автомате всегда приводит к неизоморфному автомату. В приведены структуры не сильно связных автоматов, в которых возможна переброска k дуг при любом k>1. В показано, что существуют сильно связные автоматы и переброски, сохраняющие изоморфизм, однако пока не удалось построить автомат с двумя такими перебросками. В дальнейшем, если не оговорено противное, под автоматом понимается автономный автомат. Неопределяемые понятия можно найти в.
Утверждение 1. Для любого автономного сильно связного приведенного автомата не существует переброски 2-х дуг, сохраняющей изоморфизм.
Утверждение 2. Для любого автономного не сильно связного приведенного автомата, представляющего собой несколько сильно связных компонент, не существует переброски 2-х дуг, сохраняющей изоморфизм.
Утверждение 3. Существует автономный не сильно связный приведенный автомат, допускающий переброску 2-х дуг, сохраняющую изоморфизм.
Эти утверждения основаны на том факте, что в общем случае граф переходов автономного автомата представляет собой набор компонент связности, причем каждая компонента является циклом с входящими в него деревьями. Если автомат сильно связен, то его граф переходов превращается в простой цикл. С другой стороны, цикл можно рассматривать как автономный групповой автомат, т.е. автомат, у которого {δ(s,x)|s∈S}=S.
Утверждение 4. Пусть А – автономный групповой автомат с n состояниями. Тогда:
Заметим, что утверждения, аналогичные утверждениям 1 и 2, справедливы и для циклических орграфов без отметок на дугах.