Автоматів теорія

Автома́тів тео́рія — логіко-математична теорія, об’єктом дослідження якої є абстрактні дискретні автомати — покрокові перетворювачі інформації (див. Автомат у математиці).

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

Проблематика теорії автоматів почала складатися в 1930-х у межах теорії алгоритмів і теорії релейних пристроїв. Сформульоване (1936) поняття обчислювального автомата (або машини Тюрінга) дало змогу формально уточнити інтуїтивне поняття алгоритму. Тобто А. Тюрінг формалізував правила виконання дій за допомогою опису роботи певної конструкції.

Основи теорії автоматів закладено в 1950-х під впливом запитів проектування обчислювальних і керувальних машин, а також внутрішніх потреб теорії алгоритмів і математичної логіки. Наприкінці 1950-х лінгвіст Н. Хомський запропонував формальні правила опису структури виразів мов — граматики, які виявилися тісно пов’язаними з автоматами й забезпечили значний внесок у теорію автоматів.

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

Абстрактно-алгебраїчна теорія автоматів досліджує властивості автоматів і способи їхнього зображення, розробляє підходи до розв’язання проблем створення алгебраїчних алгоритмів і побудови апарата для формальних перетворень виразів у цих алгебрах, що дає змогу розв’язувати, зокрема, оптимізаційні завдання в проектуванні дискретних пристроїв і програм. В абстрактно-алгебраїчній теорії автоматів виокремлюють теорію скінченних автоматів (СА) і теорію нескінченних автоматів. У теорії СА фундаментальною є теорема С. Кліні, яка характеризує формальні мови, задані СА за допомогою алгебраїчних засобів. Доведення теореми Кліні дає розв’язання двох центральних проблем — аналізу (описування поведінки автомата на основі його заданої програми або структури) і синтезу (створення автомата, вимоги до поведінки якого можна описати в певний спосіб). Для СА вимоги до поведінки — це опис множини слів, які він має допускати, у вигляді регулярного виразу. Це вираз в алгебрі, елементами якої є множини слів, що розпізнаються СА, а операціями є об’єднання, конкатенація та ітерація. Для алгебри регулярних множин не існує скінченної повної системи тотожностей.

У теоріях автоматів, як скінченних, так і нескінченних, важливим є поняття недетермінізму, що полягає в неоднозначності поведінки автоматів. Детермінований абстрактний автомат, що перебуває в деякому стані й отримує вхідний символ, може перейти лише в один зі своїх станів і видати тільки один з вихідних символів. Натомість недетермінований автомат, що перебуває в деякому стані й має символ на вході, може перейти в будь-який стан з певної їх множини та видати будь-який з деякої множини вихідних символів. Тобто автомат-перетворювач відображає вхідне слово в деяку множину вихідних слів, кожне з яких може бути видано автоматом. Недетермінований автомат-розпізнавач, сприйнявши вхідне слово, може опинитися в будь-якому стані з деякої їх множини. Він допускає вхідне слово, якщо серед цих станів є хоча б один кінцевий. Недетерміновані автомати важливі в дослідженні властивостей автоматних перетворень і формальних мов. Зокрема, в теорії СА встановлено, що множини формальних мов, що їх задають недетерміновані й детерміновані СА (НСА й ДСА), збігаються; точніше, створено алгоритм, який для будь-якого НСА будує ДСА, що задає таку саму мову. Цей алгоритм та алгоритм синтезу НСА за регулярним виразом є простими й утворюють основу для практичного синтезу ДСА.

Для будь-яких обчислювальних моделей одними з найважливіших є проблеми еквівалентності, мінімізації та побудови повної системи еквівалентних перетворень. Проблеми еквівалентності та мінімізації ДСА мають ефективні алгоритми розв’язання. Доведено, що скінченої повної системи еквівалентних перетворень для СА не існує. Важливою є також лема про розростання: якщо в регулярній мові є достатньо довге слово, то в ньому знайдеться підслово, довільна кількість повторень якого (розростання) у слові дає слова цієї самої регулярної мови. Тому використання цієї леми часто призводить до помилкового припущення, що деяка мова є регулярною, коли вже було доведено, що вона не є такою У теорії нескінченних автоматів, тісно пов’язаній з теорією формальних мов і граматик і з теорією алгоритмів, виокремлюють та вивчають класи нескінченних автоматів спеціального вигляду.

Найбільш дослідженим є клас автоматів із магазинною пам’яттю (МПА), у якому виокремлено низку підкласів, важливість яких полягає в існуванні ефективних алгоритмів визначення належності слова заданій мові, тобто синтаксичного аналізу слів.

Для класу МПА сформульовано низку важливих тверджень. МПА та контекстно-вільні граматики (КВ-граматики) мають однакову потужність з погляду множини мов, що ними задаються. Детерміновані й недетерміновані МПА (ДМПА і НМПА) задають різні класи мов. Існує підклас КВ-граматик, які породжують у точності мови, задані ДМПА. Останні два твердження важливі для практики, адже саме ДМПА є математичною моделлю синтаксичних аналізаторів у трансляторах мов програмування. Проблема еквівалентності в класі НМПА є нерозв’язною, а для класу ДМПА алгоритм її розв’язання побудовано більш ніж через 30 років після формулювання самої проблеми.

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

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

• дослідження з асимптотичних оцінок їхньої складності;

• розв’язання проблеми повноти системи елементарних автоматів;

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

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

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

Великий внесок у розвиток теорії автоматів зробили академік В. Глушков і колектив очолюваного ним Інституту кібернетики НАН України.

Література

1. Глушков В. М. Введение в кибернетику. Киев, 1964.
2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Москва, 1978. Т. 1.
3. Карпов Ю. Г. Теория автоматов. Санкт-Петербург, 2002.
4. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. Москва, 2002.

Автор ВУЕ

• А. Б. Ставровський