Содержание

• Введение
• 1. Актуальность темы
• 2. Автоматная модель
• 3. Постановка задачи
• 4.Примеры переброски дуг
• 5.Связь циклической структуры и поведения автомата
• 6.Обзор результатов
• Выводы
• Список источников

Введение

Сложные системы, взаимодействующие со средой, могут подвергаться деформирующим воздействиям с её стороны. Эти воздействия могут приводить к изменениям структуры систем и, как следствие, к изменениям их поведения. В связи с этим возникают задачи анализа поведения систем, которые подверглись таким искажающим воздействиям. Одной из основных математических моделей систем является модель конечного автомата. Вышеуказанные задачи анализа поведения в рамках автоматной модели изучаются в теории экспериментов с автоматами, технической диагностике, теории синтеза дискретных систем, где они являются ключевыми.

1. Актуальность темы

В частности, задача анализа поведения становится всё более актуальной в связи с широким внедрением различных микроэлектронных систем и компонент критического применения и повышенными требованиями к достижению необходимого уровня безопасности [1].

При анализе поведения автоматных систем важное место занимает задача описания и изучения класса автоматов, которому принадлежит исследуемый по поведению автомат. Обычно эта задача рассматривается в рамках теории экспериментов с автоматами. Традиционно контрольные и распознающие эксперименты строятся для случая класса всех автоматов с n состояниями или его подклассов. Многие такие классы можно описать как результат порождения автоматов класса из заданного автомата — эталона с помощью операции переброски дуг в его графе переходов. Например, класс локально порожденных автоматов [2], классы автоматов, порождаемых константными неисправностями в их схемной реализации, и ряд других можно описать указанным образом.

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

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

2. Автоматная модель

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

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

3. Постановка задачи

Основные определения теории автоматов можно найти в [7].

Под автоматом будем понимать автомат Мили, который является конечным автоматом, выходная последовательность которого (в отличие от автомата Мура) зависит от состояния автомата и входных сигналов. Это означает, что в графе состояний каждому ребру соответствует некоторое значение (выходной символ). В вершины графа автомата Мили записываются выходящие сигналы, а дугам графа приписывают условие перехода из одного состояния в другое, а также входящие сигналы. Автомат Мили можно описать пятеркой A= (S, X, Y, δ, λ), где S, X, Y — алфавиты состояний, входных и выходных символов соответственно, а δ, λ функции переходов и выходов. Функции δ и λ обычным образом распространяются на множество X* всех входных слов конечной длины. Для удобства множество состояний автомата и сам автомат будем обозначать одной буквой: A = (А, X, Y, δ, λ). Автомат A будем рассматривать также как множество дуг Ea, где дуга — это четверка (s,x,y,t), где s — начальная вершина, x — входной символ, y — выходной символ, t — конец дуги, если δ(s,x) = t, λ(s,x) = y.

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

В дальнейшем будем рассматривать автоматы A и В, у которых входные и выходные алфавиты совпадают, то есть 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).

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

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

По своей структуре автомат — это конечный ориентированный граф. Путь в автомате — это оследовательность дуг ( a₁, x₁,y₁, b₁ ) (a₂, x₂,y₂, b₂ ) … (a_n, x_n,y_n, b_n ), в которой соседние дуги имеют общую инцидентную вершину: a₂=b₁, a₃=b₂…a_n=b_n-1, и каждая дуга встречается ровно один раз. Число дуг n называется длиной пути. Состояние a1 называется началом пути, а bn — его концом. При этом говорят, что состояние bn достижимо из a1. Путь, каждая вершина которого принадлежит не более чем двум его дугам, называется простым. Циклом (простым циклом) называется путь (простой путь), в котором начальная и конечная вершины совпадают. Автомат, в котором каждая пара состояний достижима друг из друга, называется сильно связным. Пара состояний, каждое из которых достижимо из другого, называется взаимно достижимыми. Отношение взаимной достижимости является эквивалентностью на множестве состояний. Классы отношения взаимной достижимости называются компонентами сильной связности автомата или сильными компонентами.

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

На основании ранее проведенных исследований [4, 5, 6] к настоящему времени известны следующие результаты:

• переброска одной дуги всегда приводит к неизоморфному автомату;

• при переброске двух дуг входные — выходные отметки на перебрасываемых дугах должны совпадать;

• показана структура автоматов, в которых возможна переброска любого числа дуг ≥ 2. Эти автоматы не являются сильно связными;

• доказаны достаточные условия изоморфизма автоматов при переброске двух дуг.

А не известно следующее:

• существует ли сильно связный автомат, допускающий переброску при сохранении поведения;

• необходимые условия для сохранения поведения;

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

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

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

В [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. Пример изоморфизма автоматов при переброске двух дуг
(анимация: 6 кадров, 5 циклов повторения, 71,4 килобайт)

В данном примере компоненты сильной связности автомата А – это множества состояний {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′ является изоморфизмом автомата А на автомат А′.

Рисунок — 2. Пример изоморфизма автоматов при переброске четырех дуг в сильно связном автомате

5. Связь циклической структуры и поведения автомата

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

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

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

   Состояние 1 в автомате А имеет две одинаково направленных дуги (ведущих в состояние 2). А в автомате А′ таких состояний на одно меньше. Отсюда следует нарушение изоморфизма А и А′.

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

На основании ранее проведенных исследований [4, 5, 6] к настоящему времени известны следующие результаты:

• переброска одной дуги всегда приводит к неизоморфному автомату;

• при переброске двух дуг входные - выходные отметки на перебрасываемых дугах должны совпадать;

• показана структура автоматов, в которых возможна переброска любого числа дуг ≥2. Эти автоматы не являются сильно связными;

• доказаны достаточные условия изоморфизма автоматов при переброске двух дуг.

6. Обзор результатов

Получены следующие результаты:

1. анализ циклической структуры в случае автономного автомата (у которого |Х|=1) позволил доказать, что переброска одной дуги в автономном автомате невозможна (пример 3);
2. найдены примеры сильно связных автоматов, в которых существует ≥4–х перебросок, сохраняющих изоморфизм (пример 2);
3. пока не удалось построить автомат с двумя такими перебросками;
4. показано, что возможны переброски более 2–х дуг, при которых входные–выходные отметки на перебрасываемых дугах различны (пример 2).

Выводы

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

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

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

При написании данного реферата магистерская работа еще не завершена. Окончательное завершение: январь 2014 года. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.

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

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