Абстрактна теорія автоматів
Матеріал з Вікіпедії — вільної енциклопедії.
Абстрактна теорія автоматів — напрям в теорії автоматів, який характеризується тим, що при вивченні автоматів не беруть до уваги їх структурні особливості. За такого підходу, внутрішні стани автомата, його вхідні та вихідні сигнали розглядаються як деякі абстрактні символи, які утворюють відповідно алфавіти: Q (внутрішній), X (вхідний), Y (вихідний). X та Y вважаються скінченими алфавітами. Q може бути нескінченним.
[ред.] Поняття абстрактної теорії автоматів
Детермінований автомат визначається як кортеж M = <Q, X, Y, Φ, Ψ>, де функція переходів Ψ відображає декартів добуток Q×X в Q, а функція виходів Φ відображає Q×X в Y.
Недетермінований автомат визначається аналогічно, але з тою різницею, що в якості Φ, Ψ допускаються багатозначні функції.
В випадку Імовірнісного автомата, під Φ, Ψ слід розуміти матриці перехідних та вихідних імовірностей, тобто функції, які відображають Q×X×Q та Q×X×Y в числовий проміжок (0,1) та мають відповідно смисл Ψ (qi, xj, qs) - імовірність того, що xj переводить стан qi в стан qs, Φ (qi, xj, yr) - імовірність того, що при вхідному символі xj та внутрішньому стані qi буде виданий вихідний символ yr.
Наведені поняття є достатньо загальними і не конструктивні у випадку, коли Q є нескінченним. Більш вузькі класи можуть бути виділені шляхом накладання певних обмежень на компоненти Q, X, Y, Φ, Ψ. Оскільки ці обмеження не формулюються в структурних термінах, то вони стосуються головним чином потужності алфавітів (наприклад, якщо Q скінчений, то і автомат називається скінченним) або загальних властивостей функцій Φ, Ψ.
У випадку виродження, коли той чи інший алфавіт складається з одного символа, зручніше розглядати модифіковані визначення, які отримуються при видаленні вироджених компонент. Наприклад, детермінований автомат без виходу - це трійка <Q, X, Ψ>, де Q, X, Ψ - мають звичайне значення; імовірнісний автономний автомат - це пара <Q, Ψ>, де Ψ - матриця перехідних імовірностей для станів з Q (тобто такий автомат є ланцюгом Маркова).
В абстрактній теорії автоматів вивчаються переважно такі концепції поведінки (див. Поведінка автоматів), в яких слова, що перетворюються або приймаються, є словами з алфавіту X (вхідні слова), а результатами перетворення або породження є слова в алфавіті Y (вихідні слова). Переважно це - реалізація операторів в автоматі та представлення множин в реальний час.
Враховуючи велику загальність та неконструктивність використовуваних визначень автомата, навіть в випадку детермінованих автоматів, оператори, що реалізуються (тобто множини, що представляються) можуть виявитись неефективними.
В абстрактній теорії автоматів основними конструктивними об'єктами для вивчення є скінченні автомати, а також реалізовані ними оператори та множини, які ними представляються (скінченно-автоматні оператори та множини). В абстрактній теорії автоматів широко застосовуються методи та поняття алгебри, математичної логіки та теорії алгоритмів.
Центральними проблемами абстрактної теорії, які породжені практичними завданнями конструювання та експлуатації обчислювальної техніки та отримали належний теоретичний розвиток, є проблеми синтезу та аналізу, а також пов'язана з ними теорія експериментів з автоматами.
[ред.] Аналіз та синтез автоматів
Проблема синтезу полягає в пошуку та побудові автомата, виходячи з умов, які накладаються до реалізованого ним оператора або до множини, яка ним представляється. Тут маються на увазі реалізація або представлення в реальний час. Зазвичай вважається, що ці умови виражені на достатньо чіткій та формалізованій мові (тобто мові заказника), наприклад в вигляді формули U цієї мови.
Крім того, вважається, що шуканий автомат належить до заздалегідь окресленого класу автоматів, які дозволяють конструктивний опис. Формальна мова, засобами якої здійснюється цей опис (мова виконавця), також вважається заданою. Коли мова йде про скінченні автомати, зазвичай, опис автомата полягає в представленні системи його команд шляхом графічного або табличного задання функцій Φ, Ψ (матриць перехідних та вихідних імовірностей, якщо автомат імовірнісний). Побудований в результаті абстрактного синтезу автомат може бути використаний надалі як вихідний матеріал на етапі структурного синтезу автомата.
В межах загальної проблеми абстрактного синтеза виникають окремі проблеми:
- Існування. Чи існує оператор, який задовольняє умові, заданій формулою U, та такою, що реалізується в автоматі даного типу?
- Одиничність. Чи одиничний такий оператор?
- Конструкція. Для якого-небудь оператора, який задовольняє умові U, побудувати автомат, який його реалізує та вказати відповідне налаштування: початковий стан, завершальні стани, а в випадку імовірнісного автомата - дозволений рівень надійності.
- Мінімізація. Побудований автомат M привести за допомогою еквівалентних перетворень до еквівалентного автомата, який задовольняє деяким критеріям оптимальності. Наприклад, в випадку скінченних автоматів - мінімізація кількості станів шляхом склеювання нерозрізнених та видалення недосяжних станів.
Вирішення цих проблем реалізується в формі алгоритмів, які за заданою формулою U надають відповіді на запитання 1-2 та здійснюють необхідні конструкції та перетворення для проблем 3-4. Відповідна теорія істотно залежить від мов, які застосовуються замовником. В якості мови виконавця зазвичай розглядаються різні класи автоматних діаграм. При обранні мови замовника природньо слід керуватись наступними двома (антагоністичними) вимогами: виразність мови, тобто зручність (для замовника) викладення в ньому умов, яким повинна задовольняти поведінка автомата, простота алгоритмів, які вирішують проблему синтеза в цілому та окремі її завдання (аналогія в програмуванні - виразність вхідної мови та простота транслятора). Ця ситуація докладно вивчена в застосуванні до скінченних автоматів. З точки зору простоти алгоритмів кращими є алгебраїчні мови (див. Регулярні події та вирази). Більш виразними є мови, які базовані на застосуванні фрагментів логіки предикатів (див. Логічна мова для задання автоматів), але й алгоритми синтезу для них стають більш громіздкими.
Проблема аналізу є оберненою до проблеми синтезу: за завданим автоматом потрібно описати його поведінку засобами мови замовника. В певному сенсі аналіз та синтез можна розглядати як переклади з однієї мови на іншу, при цьому переклад, який відповідає аналізові, переважно легший. Розроблено багато алгоритмів синтезу та аналізу, головним чином для скінченних детермінованих автоматів. В якості складової частини алгоритма синтезу детермінованого автомату в нього зазвичай входить побудова недетермінованого автомата з наступним його перетворенням в еквівалентний йому детермінований автомат. Розробка алгоритмів абстрактного синтезу з застосуванням логічних мов виявилась пов'язаною з деякими алгоритмічними проблемами математичної логіки та сприяла їх вирішенню.
![]() |
Цю сторінку необхідно дописати чи вдосконалити. Саме Ви можете допомогти проекту, зробивши це! |