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

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

Анотація: Наводяться початкові відомості про абстрактні автоматах Мілі і Мура. Даються можливі способи подання автоматів: теоретико-множинне, графові, табличний і матричне.

Вступ

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

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

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

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

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

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

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

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

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

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

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

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

Приклад 11. Автомат, що описує поведінку "розумного" батька.

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

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

- лаяти сина;

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

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

- радіти;

- радіти.

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

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

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

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

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

- стану;

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Автомат першого роду (автомат Мілі)
2. Автомат другого роду (автомат Мура)