Назад в библиотеку

О локальных преобразованиях автономных автоматов

Авторы: О.М. Копытова
Источник: Материалы ХІ международной научно-практической конференции Математическое и программное обеспечение интеллектуальных систем (MPZIS-2013). Днепропетровск, 20-22 ноября 2013. – С. 119-120.

Основной материал

В работе продолжается изучение автоматов, устойчивых по поведению к локальной операции – переброске дуг. Под автоматом [1] понимается приведенный автомат Мили A = (S,Х,Y,δ,λ), где S, Х, Y – множества состояний, входных и выходных символов соответственно, а δ, λ – функции переходов и выходов. Если Х={x}, т.е. x – единственный входной символ, то автомат называется автономным. Пусть е=(s,x′,y′,s1) – дуга в графе переходов автомата А. Переброской дуги е в состояние s2, отличное от s1, называем замену этой дуги на дугу (s, x′, y′, s2). Пусть автомат А′ получен из автомата А переброской некоторого множества его дуг. Если при этом автомат А′ остается изоморфным исходному автомату A, то говорим, что переброска сохраняет изоморфизм. Задача заключается в том, чтобы исследовать структуру циклов в автомате и найти условия, при которых существуют переброски, сохраняющие изоморфизм.

В [1] доказано, что переброска одной дуги в любом приведенном автомате всегда приводит к неизоморфному автомату. В [2] приведены структуры не сильно связных автоматов, в которых возможна переброска k дуг при любом k>1. В [3] показано, что существуют сильно связные автоматы и переброски, сохраняющие изоморфизм, однако пока не удалось построить автомат с двумя такими перебросками. В дальнейшем, если не оговорено противное, под автоматом понимается автономный автомат. Неопределяемые понятия можно найти в [1].

Утверждение 1. Для любого автономного сильно связного приведенного автомата не существует переброски 2-х дуг, сохраняющей изоморфизм.

Утверждение 2. Для любого автономного не сильно связного приведенного автомата, представляющего собой несколько сильно связных компонент, не существует переброски 2-х дуг, сохраняющей изоморфизм.

Утверждение 3. Существует автономный не сильно связный приведенный автомат, допускающий переброску 2-х дуг, сохраняющую изоморфизм.

Эти утверждения основаны на том факте, что в общем случае граф переходов автономного автомата представляет собой набор компонент связности, причем каждая компонента является циклом с входящими в него деревьями. Если автомат сильно связен, то его граф переходов превращается в простой цикл. С другой стороны, цикл можно рассматривать как автономный групповой автомат, т.е. автомат, у которого {δ(s,x)|s∈S}=S.

Утверждение 4. Пусть А – автономный групповой автомат с n состояниями. Тогда:

1) при n≥3 в автомате А существует переброска k дуг, сохраняющая изоморфизм, для всех 3≤k≤n;

2) при n≤2 в автомате А не существует переброски k дуг, сохраняющей изоморфизм, где 1≤k≤2.

Заметим, что утверждения, аналогичные утверждениям 1 и 2, справедливы и для циклических орграфов без отметок на дугах.

Литература

  1. Грунский И.С., Козловский В.А. Синтез и идентификация автоматов. – Киев: Наукова думка, 2004. – 246 с.
  2. Копытова О.М. О структуре автоматов, сохраняющих поведение при перебросках дуг. Труды VIII Международной конференции Дискретные модели в теории управляющих систем. Москва: Макс-Пресс, 2009. – C. 155–159.
  3. Бурлаева Е.И., Копытова О.М. Об одном типе локальных преобразований конечного автомата // Материалы IV всеукраинской научно-технической конференции студентов, аспирантов и молодых ученых «Информационные управляющие системы и компьютерный мониторинг (ИУС КМ 2013)» ( 24.04-25.04.2013). Донецк: ДонНТУ, 2013. – C. 479–484.