НОУ ІНТУІТ, Лекція, Основні поняття теорії абстрактних автоматів

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

Теорія автоматів має широкі можливості застосування:

Проектування систем логічного керування;
Обробка текстів та побудова компіляторів;
Специфікація та верифікація систем взаємодіючих процесів;
Мови опису документів та об'єктно-орієнтованих програм;
Оптимізація логічних програм

Про це можна судити з виступів на семінарі "Software 2000 ..." вчених та фахівців.

Дуг Росс: "…80 і навіть 90 % інформатики ( Computer Science ) у майбутньому ґрунтуватися на теорії кінцевих автоматів…"

Herver Gallaire: "Я знаю людей з "Боїнга", які займаються системами стабілізації літаків з використанням чистої теорії автоматів. Навіть важко собі уявити, що їм вдалося за допомогою цієї теорії."

Brian Randell: "Більшість теорії автоматів була успішно використана в системних програмах і текстових фільтрах в ОС UNIX. Це дозволяє безлічі людей працювати на високому рівні і розробляти дуже ефективні програми".

1.1. Основні поняття та визначення.

Найпростіший перетворювач інформації (рис.1.1,а) відображає деяку множину елементів інформації Х , що надходить на вхід, деяка множина на виході Y . Якщо множини Х і Y є кінцевими і дискретними, тобто перетворення здійснюється в дискретні моменти часу, такі перетворювачі інформації називаються кінцевими перетворювачами. Елементи множин Х і Y в цьому випадку попередньо кодують двійковими кодами і будують перетворення однієї множини в іншу.

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

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

Розглянемо кілька прикладів.

Приклад 11 Карпов Ю.Г. Теорія автоматів-СПб.: Пітер, 2003. Автомат, що описує поведінку "розумного" батька.

Опишемо поведінку батька, син якого навчається у школі та приносить двійки та п'ятірки. Батько не хоче хапатися за ремінь щоразу, як тільки син отримає двійку, і вибирає тоншу тактику виховання. Задамо такий автомат графом , у якому вершини відповідають станам, а дуга зі стану s стан q , позначене x/y , проводиться тоді, коли автомат зі стану s під впливом вхідного сигналу х переходить у стан q з вихідною реакцією y . Граф автомата, що моделює розумну поведінку батька, представлений на рис.1.2. Цей автомат має чотири стани, два вхідні сигнали - оцінки та вихідні сигнали, які інтерпретуватимемо як дії батька наступним чином:

- брати ремінь;

- лаяти сина;

- заспокоювати сина;

- Сподіватися;

- радіти;

- тріумфувати.

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

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

Апаратну реалізацію автомата розглянемо у другій частині цього розділу.

Приклад 2. "Студент"

Автомат, модель якого представлена на рис.1.4, описує поведінку студента та викладачів.

- Стани;

- вхідні сигнали: "н", "2" та "5".

- Вихідні реакції:

- відзначаємо "н";
- заспокоювати;
- хвалимо студента;
- заохочуємо;
- Сподіваємося;
- попереджаємо;
- відраховуємо;

Приклад 3 1 . Електронний годинник (рис.1.5).

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

Регістри відображають час, дату або секундомір залежно від "Керування". Пристрій управління побудований на основі моделі кінцевого автомата. Кінцевий автомат реагує на натискання кнопки "а" на корпусі переходом у стан "Установка хвилин", в якому подія натискання кнопки "b" викликає збільшення числа. Пристрій управління побудовано на основі моделі кінцевого автомата, граф якого показаний на рис.1.6

Отже. З одного боку, АВТОМАТ - пристрій, що виконує деякі дії без участі людини. З іншого боку, АВТОМАТ - математична модель, що описує поведінку технічного устрою. У разі реальне пристрій, система тощо. розглядається як деякий "ЧОРНИЙ ЯЩИК" (рис.1.7).

Абстрактний автомат - це математична модель, що описує технічний пристрій сукупністю вхідних, вихідних сигналів та станів, крім того:

має безліч внутрішніх станів, званих станами автомата;
на вхід автомата надходить кінцеве безліч вхідних сигналів є кінцеве безліч вихідних сигналів;
задана функція переходу;
задана функція формування виходів автомата;
визначено початковий стан автомата.

Тобто для опису автомата потрібно використовувати шістку виду, де

Автомат реалізує деяке відображення безлічі слів вхідного алфавіту Z до множини слів вихідного алфавіту W .

Автомат називається кінцевим,якщо множина його внутрішніх станів і безліч значень вхідних сигналів є кінцеві множини.

Автомат називається синхронним, якщо інтервал тимчасової дискретизації постійний, інакше говорять про асинхронний автомат.

Автомат називається детермінованим, якщо поведінка автомата в кожний момент часу однозначно визначено ( ,)

Залежно від способу визначення вихідного сигналу в синхронних автоматах розрізняють: