Абстрактна теорія автоматів

Абстрактна теорія автоматів — напрям в теорії автоматів, який характеризується тим, що при вивченні автоматів не беруть до уваги їх структурні особливості. За такого підходу, внутрішні стани автомата, його вхідні та вихідні сигнали розглядаються як деякі абстрактні символи, які утворюють відповідно алфавіти: Q (внутрішній), X (вхідний), Y (вихідний). X та Y вважаються скінченими алфавітами. Q може бути нескінченним.

Поняття абстрактної теорії автоматів

Детермінований автомат визначається як кортеж M = <Q, X, Y, Φ, Ψ>, де функція переходів Ψ відображає декартів добуток Q×X в Q, а функція виходів Φ відображає Q×X в Y.

Недетермінований автомат визначається аналогічно, але з тою різницею, що як Φ, Ψ допускаються багатозначні функції.

В випадку Імовірнісного автомата, під Φ, Ψ слід розуміти матриці перехідних та вихідних імовірностей, тобто функції, які відображають Q×X×Q та Q×X×Y в числовий проміжок (0,1) та мають відповідно смисл Ψ (q_i, x_j, q_s) — імовірність того, що x_j переводить стан q_i в стан q_s, Φ (q_i, x_j, y_r) — імовірність того, що при вхідному символі x_j та внутрішньому стані q_i буде виданий вихідний символ y_r.

Наведені поняття є достатньо загальними і не конструктивні у випадку, коли Q є нескінченним. Більш вузькі класи можуть бути виділені шляхом накладання певних обмежень на компоненти Q, X, Y, Φ, Ψ. Оскільки ці обмеження не формулюються в структурних термінах, то вони стосуються головним чином потужності алфавітів (наприклад, якщо Q скінчений, то і автомат називається скінченним) або загальних властивостей функцій Φ, Ψ.

У випадку виродження, коли той чи інший алфавіт складається з одного символу, зручніше розглядати модифіковані визначення, які отримуються при видаленні вироджених компонент. Наприклад, детермінований автомат без виходу — це трійка <Q, X, Ψ>, де Q, X, Ψ — мають звичайне значення; імовірнісний автономний автомат — це пара <Q, Ψ>, де Ψ — матриця перехідних імовірностей для станів з Q (тобто такий автомат є ланцюгом Маркова).

В абстрактній теорії автоматів вивчаються переважно такі концепції поведінки (див. Поведінка автоматів), в яких слова, що перетворюються або приймаються, є словами з алфавіту X (вхідні слова), а результатами перетворення або породження є слова в алфавіті Y (вихідні слова). Переважно це — реалізація операторів в автоматі та представлення множин в реальний час.

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

В абстрактній теорії автоматів основними конструктивними об'єктами для вивчення є скінченні автомати, а також реалізовані ними оператори та множини, які ними представляються (скінченно-автоматні оператори та множини). В абстрактній теорії автоматів широко застосовуються методи та поняття алгебри, математичної логіки та теорії алгоритмів.

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

Аналіз та синтез автоматів

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

Крім того, вважається, що шуканий автомат належить до заздалегідь окресленого класу автоматів, які дозволяють конструктивний опис. Формальна мова, засобами якої здійснюється цей опис (мова виконавця), також вважається заданою. Коли мова йде про скінченні автомати, зазвичай, опис автомата полягає в представленні системи його команд шляхом графічного або табличного задання функцій Φ, Ψ (матриць перехідних та вихідних імовірностей, якщо автомат імовірнісний). Побудований в результаті абстрактного синтезу автомат може бути використаний надалі як вихідний матеріал на етапі структурного синтезу автомата.

В межах загальної проблеми абстрактного синтезу виникають окремі проблеми:

1. Існування. Чи існує оператор, який задовольняє умові, заданій формулою U, та такою, що реалізується в автоматі даного типу?
2. Одиничність. Чи одиничний такий оператор?
3. Конструкція. Для якого-небудь оператора, який задовольняє умові U, побудувати автомат, який його реалізує та вказати відповідне налаштування: початковий стан, завершальні стани, а в випадку імовірнісного автомата — дозволений рівень надійності.
4. Мінімізація. Побудований автомат M привести за допомогою еквівалентних перетворень до еквівалентного автомата, який задовольняє деяким критеріям оптимальності. Наприклад, в випадку скінченних автоматів — мінімізація кількості станів шляхом склеювання нерозрізнених та видалення недосяжних станів.

Розв'язання цих проблем реалізується в формі алгоритмів, які за заданою формулою U надають відповіді на запитання 1-2 та здійснюють необхідні конструкції та перетворення для проблем 3-4. Відповідна теорія істотно залежить від мов, які застосовуються замовником. Як мови виконавця зазвичай розглядаються різні класи автоматних діаграм. При обранні мови замовника природно слід керуватись такими двома (антагоністичними) вимогами: виразність мови, тобто зручність (для замовника) викладення в ньому умов, яким повинна задовольняти поведінка автомата, простота алгоритмів, які розв'язують проблему синтезу в цілому та окремі її завдання (аналогія в програмуванні — виразність вхідної мови та простота транслятора). Ця ситуація докладно вивчена в застосуванні до скінченних автоматів. З точки зору простоти алгоритмів найкращими є алгебраїчні мови (див. Регулярні події та вирази). Виразнішими є мови, які базовані на застосуванні фрагментів логіки предикатів (див. Логічна мова для задання автоматів), але й алгоритми синтезу для них стають громіздкішими.

Проблема аналізу є оберненою до проблеми синтезу: за завданим автоматом потрібно описати його поведінку засобами мови замовника. В певному сенсі аналіз та синтез можна розглядати як переклади з однієї мови на іншу, при цьому переклад, який відповідає аналізові, переважно легший.

Розроблено багато алгоритмів синтезу та аналізу, головним чином для скінченних детермінованих автоматів. Як складова частина алгоритму синтезу детермінованого автомату в нього зазвичай входить побудова недетермінованого автомата з наступним його перетворенням в еквівалентний йому детермінований автомат. Розробка алгоритмів абстрактного синтезу з застосуванням логічних мов виявилась пов'язаною з деякими алгоритмічними проблемами математичної логіки та сприяла їх вирішенню.

Алгоритми синтезу скінченних автоматів

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

Основний алгоритм синтезу скінчених автоматів

Нехай потрібно побудувати алгоритм, який дозволяв би за будь-якого кінцевого безлічі М регулярних подій, заданих своїми регулярними виразами, знаходити таблицю переходів і виходів кінцевого цілком певного автомата Мілі та зазначену таблицю переходів кінцевого цілком певного А таких, що всі події множини M представляються як в автоматі Мілі, так і в автоматі Мура деякими множинами їх вихідних сигналів. Перейдемо від подання подій R1, ..., Rp в автоматі Мура множинами станів до подання їх множинами вихідних сигналів. Для цього достатньо як вихідні сигнали взяти різні підмножини заданої множини подій (R1, ..., Rp) і відзначати кожне стан q автомата безліччю тих подій, які містять слова, що переводять автомат з початкового стану в стан q.

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

Місцями в правильно записаному регулярному виразі R над алфавітом

X = (x1, ..., xn)

домовимося називати спеціально введені знаки розділу (вертикальні лінії), що ставляться між будь-якими двома знаками цього виразу (знаками у виразі R є букви алфавіту Х, символ порожнього слова ε, знак диз'юнкції, ітераційні і звичайні дужки). Крім цих так званих роздільних місць (знаків розділу) вводиться ще два місця - початкове і кінцеве. Перше їх них розташовується зліва від самого лівого знака виразу R, а друге - праворуч від самого правого знака.

Наприклад, R = z ∨ x {y ∨ z}, де R - регулярний вираз. Наведемо цей вираз у правильній формі

R = (z ∨ x {y ∨ z}).

Проведемо розмітку:

| (| Z | ∨ | x | {| y | ∨ | z |} |) | (1)

1 2 3 4 5 6 7 8 9 10 11.

З виразу (1) видно, що регулярний вираз R має 11 місць.

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

Для прикладу розглянемо процеси розгортання розміченого вище вираження R в належать акредитуючій їм події слова z і xyz.

При розгортанні вираження в перше слово необхідно здійснити безпосередній перехід від початкового місця 1 до місця 2, перехід через букву z від місця 2 до місця 3 та безпосередній перехід від 3 до кінцевого місця 11.

При розгортанні вираження в слово xyz порядок переходів буде наступний: безпосередній перехід від місця 1 до місця 4 перехід через букву x - від 4 до 5, безпосередній перехід - від 5 до 6, перехід через букву у - від 6 до 7, безпосередній перехід від 7 до 10, безпосередній перехід від 10 до 8, перехід через букву z - від 8 до 9, безпосередній перехід від 9 до 10 і безпосередній перехід від 10 до 11.

Нехай R - регулярний вираз, q = xi1 xi2 ... xik довільне слово у вхідному алфавіті події, репрезентованої виразом R.

Домовимося, що місце α у вираженні R пов'язано словом q з місцем β в тому ж вираженні, якщо від місця α до місця β можна перейти за допомогою чергування будь-якого числа безпосередніх переходів і переходів через букви xi1, xi2, ..., ск слова q, взятих по одному разу в тому порядку, в якому вони входять в слово. Ця умова означає, що місце β q-слід за місцем α щоразу, коли α пов'язане з місцем β словом q.

Також домовимося говорити, що місце β підпорядковане місцем α, якщо від місця α до місцем β можна перейти за допомогою одних лише безпосередніх переходів, тобто якщо місце α пов'язане з місцем β порожнім словом ε.

Правила побудови основного алгоритму синтезу скінчених автоматів

1. Задані регулярні події (число яких передбачається кінцевим) представляються правильно записаними регулярними виразами R1, ..., Rp. Все місця (як основні, так і не основні) в цих виразах позначаються вертикальними рисками (лініями).
2. Кожному основним місцем у виразах ${\displaystyle R_{1},\ldots ,R_{p}}$ приписується як індекс невід'ємне ціле число. При цьому всім початковим місцям приписується один і той же індекс (нуль). Що ж до інших основних місць, то вони нумеруються в довільному порядку натуральними числами 1, 2, ... Всі введені тут індекси називаються основними. Основні індекси підписуються під вертикальними рисами відповідних їм (основних) місць і підкреслюються знизу загальною для кожного з виразів ${\displaystyle R_{1},\ldots ,R_{p}}$ горизонтальною розділовою рисою.
3. Індекс (основний) кожного основного місця α поширюється як неосновний індекс на всі місця (як основні, так і неосновні), підлеглі місцю α, але відмінні від нього самого.

Джерела

• Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973.
• «Синтез цифровых автоматов», Н. Г. Захаров, В. Н. Рогов, Ульяновск 2003.

Див. також

• Портал «Математика»

• Теорія автоматів
• Автоматні відображення