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

---

ОБ ОДНОМ ТИПЕ ЛОКАЛЬНЫХ ПРЕОБРАЗОВАНИЙ КОНЕЧНОГО АВТОМАТА

Авторы: Е.И. Бурлаева, О.М. Копытова
Источник: Материалы IV всеукраинской научно–технической конфиренции студентов, аспирантов и молодых ученых Информационные управляющие системы и компьютерный мониторинг (ИУС КМ 2013) (24.04–25.04.2013). Донецк, ДонНТУ. – 2013. – С. 479–484.

Аннотация

Бурлаева Е.И. Копытова О.М. Об одном типе локальных преобразований конечного автомата. Рассматривается специальная операция на дугах конечного автомата – переброска дуг. Автоматы, которые можно описать как результат переброски группы дуг в некотором автомате–эталоне, могут рассматриваться как его "неисправности". Приводятся примеры, когда в результате переброски автомат не изменяет своего поведения, оставаясь изоморфными исходному автомату. Исследуется циклическая структура таких автоматов.

Ключевые слова: автомат, поведение, переброска дуг, изоморфизм.

Введение

Модель конечного автомата лежит в основе и цифровых вычислительных устройств, и их программного обеспечения. Эта модель оказывается также полезной при описании информационного взаимодействия объектов самой разной природы, включая и технические задачи построения управляющих систем, и задачи описания поведения любых объектов, основными характеристиками которых является понятия состояния, входного стимула и реакции на него. Математический аппарат теории автоматов напрямую применяется как при разработке формальных языков (в том числе и языков программирования), так и при написании программ (автоматное программирование), а любое вычислительное устройство можно считать частным способом практической реализации конечного автомата.

Сложные системы, поведение которых исследуется в течение, например, всего жизненного цикла, могут изменять свою структуру под влиянием среды. При этом поведение новой системы может или отличаться от поведения старой, или оставаться без изменения, несмотря на то, что структура системы претерпела изменения. Условия, при которых поведение системы остается неизменным, в определенном смысле характеризуют ее устойчивость к деформирующим влияниям внешней среды. Таким образом, возникает задача изучения таких структурных изменений, при которых поведение новой системы не изменяется по сравнению со старой. Формализация соответствующей задачи может быть выполнена в рамках теории автоматов. При этом система задается конечным автоматом, а структурные изменения – перебросками дуг в этом автомате.

Поведение автоматов, которые порождаются друг из друга с помощью перебросок дуг, исследуется уже достаточно давно. В основном эта задача рассматривалась в рамках теории экспериментов с автоматами [1]. В теории графов также рассматривались родственные задачи, где изучалась задача определения, когда один из графов (автомат) может быть получен из другого в результате некоторой последовательности перебросок дуг 2. В [3] было доказано, что переброска в точности одной дуги в приведенном автомате всегда вызывает изменение его поведения – автомат становится не эквивалентным исходному автомату. Позже влияние перебросок дуг на поведение автомата изучалось в работах [4, 5]. В настоящей работе продолжается исследование свойств автоматов, допускающих переброски дуг при сохранении поведения, с точки зрения циклической структуры их графов переходов.

Формальная постановка задачи.

Основные определения теории автоматов можно найти, например, в [4]. Под автоматом будем понимать автомат Мили A =(A,X, Y,δ, λ), где A,X, Y – алфавиты состояний, входов и выходов, соответственно, а δ, λ – функции переходов и выходов. Будем также рассматривать и частичные автоматы, у которых области определения функций переходов и выходов совпадают. Как обычно, будем обозначать автомат символом множества его состояний. Автомат A будем рассматривать также как множество дуг , где дуга – это четверка (s, x, y, t), если δ(s, x) = t, λ(s, x) = y.

Будем говорить, что вход–выходное слово w = ( p, q ) порождается состоянием a автомата А, если λ( а, р ) = q. Два состояния a и b одного и того же автомата A или двух разных автоматов, соответственно A и B, называются эквивалентными, если для всякого входного слова р ∈ X* выполняется λ( а, р ) = λ′( b, р ), где λ′ – функция выходов автомата A или B. С каждым состоянием а ассоциируется автоматное отображение lа множества входных слов во множество выходных, определяемое равенством λа ( р ) = λ(а, р) для всех р ∈ X*. Автомат называется приведенным, если все его состояния попарно неэквивалентны.

В дальнейшем будем рассматривать автоматы A и B, у которых входные и выходные алфавиты совпадают, то есть A = (A, X, Y, δ, λ) и B = (B, X, Y, δ, λ). В этом случае, как обычно, отображение φ: A → B будет называться гомоморфизмом автомата A в автомат B, если для любых a ∈ A и x ∈ X :

1)φ(δ(a,x))=δ(φ(a)x).

2)λ(a,x)=λ′(φ(a)x).

Пусть e = (a, x, y, b) – дуга автомата A и e′(φ(a),x,yφ(b)) – дуга автомата B, т.е. гомоморфизм φ индуцирует некоторое отображение множества дуг E_A во множество дуг E_B. Это отображение будем также обозначать φ и писать φ(e) = e′. Дуга e′ называется образом дуги e по гомоморфизму φ, а дуга e называется прообразом e′ по φ.

Гомоморфизм φ называется полным, если каждая дуга из B имеет прообразом некоторую дугу из A. Полный взаимно однозначный гомоморфизм A на B называется изоморфизмом, автоматы A и B называем изоморфными и обозначаем A = B.

По своей структуре автомат – это конечный ориентированный граф. Путь в автомате – это последовательность дуг ( a1, x1, y1, b1 ) ( a2, x2, y2, b2 ) … ( an, xn, yn, bn ), в которой соседние дуги имеют общую инцидентную вершину: a2= b1 , a3 =b2 ,… an=bn-1 , и каждая дуга встречается ровно один раз. Число дуг n называется длиной пути. Состояние a1 называется началом пути, а bn – его концом. При этом говорят, что состояние bn достижимо из a1. Путь, каждая вершина которого принадлежит не более чем двум его дугам, называется простым. Циклом (простым циклом) называется путь (простой путь), в котором начальная и конечная вершины совпадают. Автомат, в котором каждая пара состояний достижима друг из друга, называется сильно связным. Пара состояний, каждое из которых достижимо из другого, называется взаимно достижимыми. Отношение взаимной достижимости является эквивалентностью на множестве состояний. Классы отношения взаимной достижимости называются компонентами сильной связности автомата или сильными компонентами.

Пусть A = (A, X, Y, δ, λ) – приведенный автомат и e = (s, x′, y′, s1) – его дуга. Под переброской дуги e, например, в состояние s2 будем понимать замену этой дуги на дугу (s, x′, y′, s2). Пусть автомат A′ получен из автомата A переброской некоторого множества дуг из Ea. Задача заключается в том, чтобы исследовать структуру циклов в автомате и на основе этого определить условия, при которых автомат А′ остается изоморфным исходному автомату A.

Примеры переброски дуг.

Напомним, что переброска одной дуги всегда приводит к неизоморфному автомату. Легко привести примеры, когда переброска в автомате двух дуг также порождает новый автомат, не изоморфный исходному.

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

В настоящей работе приведен пример перебросок в сильно связном автомате, опровергающий это предположение.

Приведем ряд примеров, когда переброска не изменяет поведения исходного автомата.

Граф А′ (см. рис.1) является результатом переброски двух дуг в графе А: дуга (6, 0, 0, 8) перебрасывается в состояние 9 и заменяется дугой (6′, 0, 0, 9′), дуга (7, 0, 0, 9) заменяется дугой (7′, 0, 0, 8′). Нетрудно видеть, отображение φ: А → А′, при котором φ(1) = 1′; φ(2) = 2′; φ(3) = 3′;φ (4) = 4′; φ(5) = 5′; φ(6) = 7′; φ(7) = 6′; φ(8) = 8′; φ(9) = 9′, является изоморфизмом графа А на граф А′.

В данном примере компоненты сильной связности автомата А – это множества состояний {1,2,3,4,6,7}, {5}, {8,9}, и перебрасываемые дуги прилежат разным компонентам.

В данном примере компоненты сильной связности автомата А – это множества состояний {1,2,3,4,6,7}, {5}, {8,9}, и перебрасываемые дуги прилежат разным компонентам.

Следующий пример (см. рис.2) показывает возможность переброски дуг внутри одной сильной компоненты, поскольку сам автомат А сильно связен. Автомат А′ получается заменой следующих дуг: (3,1,0,5) на (3′,1,0,6′), (4,1,0,6) на (4′,1,0,5′), (5,1,0,1) на (5′,1,0,2′), (6,1,0,2) на (6′,1,0,1′). Нетрудно видеть, что отображение φ: А →А′, при котором φ (1) = 2′; φ(2) = 1′; φ(3) = 4′; φ(4) = 3′; φ(5) = 5v; φ(6) = 6′ является изоморфизмом автомата А на автомат А′.

Анализ связи между циклической структурой автомата и сохранением его поведения при переброске дуг

Анализ циклических свойств автомата позволяет сделать следующие выводы

1. Пусть А – автономный автомат, т.е. множество его входов состоит из единственного символа: X = {x}. Граф переходов автономного автомата в общем случае представляет собой набор компонент связности, каждая из которых является циклом с входящими в него деревьями. Каждое состояние автономного автомата порождает компоненту, являющуюся либо циклом, либо циклом с входящим в него «хвостом». Для изоморфизма необходимо, чтобы множества таких компонент по всем состояниям в автомате до и после переброски совпадали. Это возможно в единственном случае, когда перебрасывается дуга, принадлежащая хвосту и предшествующая «первому» состоянию цикла. При этом переброска должна происходить в такое состояние, которое порождает точно такую же циклическую последовательность, что и «первое» состояние цикла. Но тогда А – неприведенный автомат, содержащий пару эквивалентных состояний, что противоречит условию. Таким образом, анализ циклической структуры в случае автономного автомата позволяет доказать, что переброска одной дуги в автономном автомате невозможна. При этом легко построить автономный автомат, в котором можно перебросить, например, две дуги в «хвосте» и получить изоморфный автомат.
2. Пусть А – неавтономный автомат. Автономные автоматы вида Аi=(A,{xi},Y, δ_i, λ_i) назовем автономными компонентами автомата А. Тогда автомат А можно задавать набором его автономных компонент. Возникает вопрос: как влияет переброска на множество автономных компонент автомата. Следующий пример (см. рис.3) показывает, что возможна такая переброска, которая сохраняет множество автономных компонент автомата, но при этом приводит к неизоморфному автомату. Состояние 1 в автомате А имеет две одинаково направленных дуги (ведущих в состояние 2). А в автомате А′ таких состояний на одно меньше. Отсюда следует нарушение изоморфизма А и А′.
   
   
   

   Рисунок – 3. Пример сохранения множества автономных компонент и нарушения изоморфизма автоматов при переброске одной дуги

3. Примеры показывают, что в сильно связном автомате существуют переброски, сохраняющие изоморфизм, однако пока не удалось построить автомат с двумя такими перебросками.

Выводы

Как показывают примеры, переброска дуг, сохраняющая изоморфизм, возможна в автоматах, обладающих определенной симметрией графа переходов, которая отражается и в циклической структуре графа. Однако, пример на рис. 3 говорит о том, что анализа только комбинаций циклов в автомате недостаточно. Необходимо привлекать и другие инварианты графа переходов.

Список источников

1. Мур Э.Ф. Умозрительные эксперименты с последовательностными машинами // Автоматы. – М.: Изд–во иностр. лит., 1956. – С. 179–210.
2. Козловский В.А. О классе графов, порожденных локальными преобразованиями заданного графа // Методы и системы технической диагностики. – Саратов: Изд–во Саратов. Ун–та. – 1985. – Вып.5. – С. 65–70.
3. Грунский И.С., Копытова О.М. О структуре контрольного эксперимента для определенно–диагностируемого автомата // Теория управляющих систем.– К.: Наук.думка, 1987. – С.40–54.
4. Копытова О.М. О структуре автоматов, сохраняющих поведение при перебросках дуг. Труды VIII Международной конференции "Дискретные модели в теории управляющих систем". Москва: Макс–Пресс, 2009, с. 155–159.
5. Копытова О. М. Устойчивость автоматов к неисправностям их функции переходов / О. М. Копытова // Тр. ин–та / ИПММ АН Украины. –2010. – № 21. – С. 57–66.
6. Капитонова Ю.В., Кривий С.Л., Летичевский А.А., Луцкий Г.М., Печурин Н.К. Основы дискретной математики. – К.: Наукова думка, 2002. – 568 с.