Зміст

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

Вступ

Складні системи можуть піддаватися деформуючому впливу при взаємодії з середовищем. Ці впливи можуть призводити до змін структури систем і, як наслідок, до змін їхньої поведінки. У зв'язку з цим виникають завдання аналізу поведінки таких систем. Однією з основних математичних моделей систем є модель скінченого автомата. Вищевказані задачі аналізу поведінки в рамках автоматної моделі вивчаються в теорії експериментів з автоматами, технічній діагностиці, теорії синтезу дискретних систем, де вони є ключовими.

1. Актуальність теми

Зокрема, задача аналізу поведінки стає все більш актуальною у зв'язку з широким впровадженням різних мікроелектронних систем і компонент критичного застосування та підвищеними вимогами до досягнення необхідного рівня безпеки [1].

При аналізі поведінки автоматних систем важливе місце посідає задача опису та вивчення класу автоматів, якому належить досліджуваний за поведінкою автомат. Зазвичай ця задача розглядається в рамках теорії експериментів з автоматами. Традиційно контрольні та розпізнавальні експерименти будуються для випадку класу всіх автоматів з n станами або його підкласів. Чимало таких класів можна описати як результат породження автоматів класу із заданого автомата—еталона за допомогою операції перекидання дуг в його графі переходів. Наприклад, клас локально породжених автоматів [2], класи автоматів, породжуваних константними несправностей в їх схемній реалізації, і ряд інших можна описати зазначеним чином.

У ряді випадків системи, структура яких зазнала змін, можуть виявитися стійкими до спотворюючих впливів, зберігаючи свою поведінку незмінною. Таким чином, виникає задача вивчення таких структурних змін, за яких поведінка нової системи не змінюється в порівнянні зі старою. Формалізація відповідної задачі може бути виконана в рамках теорії автоматів. При цьому система задається скінченим автоматом, а структурні зміни - перекиданнями дуг у цьому автоматі.

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

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

Модель скінченого автомата лежить в основі і цифрових обчислювальних пристроїв, і їх програмного забезпечення. Ця модель виявляється також корисною при описі інформаційної взаємодії об'єктів самої різної природи, включаючи і технічні задачі побудови керуючих систем, і задачі опису поведінки будь—яких об'єктів, основними характеристиками яких є поняття стану, вхідного стимулу і реакції на нього. Математичний апарат теорії автоматів безпосередньо застосовується як при розробці формальних мов (у тому числі і мов програмування), так і при написанні програм (автоматне програмування), а будь—який обчислювальний пристрій можна вважати приватним способом практичної реалізації скінченого автомата.

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

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

Основні визначення теорії автоматів можна знайти в [7].

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

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

Надалі будемо розглядати автомати А і В, у яких вхідні та вихідні алфавіти збігаються, тобто A = ( A, X, Y, δ′, λ′) і B = ( B, X, Y, δ′, λ′). У цьому випадку, як звичайно, відображення φ: A→B буде називатися гомоморфізмом автомата А в автомат 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. Задача полягає в тому, щоб дослідити структуру циклів в автоматі і на основі цього визначити умови, за яких автомат А′ залишається ізоморфним вихідного автомата А.

На підставі раніше проведених досліджень [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) = 5′; φ(6) = 6′ є ізоморфізмом автомата А на автомат А′.

Малюнок — 2. Приклад ізоморфізму автоматів при перекидання чотирьох дуг в сильно зв'язковому автоматі

5. Зв'язок циклічної структури і поведінки автомата

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

1) Нехай А – автономний автомат, тобто безліч його входів складається з єдиного символу: 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 с.