Материал: discrete_mathematics

5.1.Поняття скінченного автомата. Методи задання автоматів

Скiнченним автоматом (далі – просто автоматом) називають систему

A = (X, Y, U, δ, λ),

у якій X = {x1, x2, …, xm} та Y = {y1, y2, …, yn} – скінченні

жини (алфавіти) відповідно вхідних і вихідних сигналів, U = {a1, a2, …, as} – множина внутрішніх станів автомата. Функ-

ції δ та λ описують алгоритм функціонування (поведінку) автомата A. Функцію δ: U × X → U називають функцією переходів, а

λ: U × X → Y – функцією виходів автомата A.

Необхідно підкреслити одну особливість моделі автомата, яка випливає з її подальшої фізичної інтерпретації. Вважаємо, що автомат A функціонує в дискретному часі, тобто час функціонування автомата розбито на відрізки однакової довжини – та кти. Межи тактів t називають моментами абстрактного дискретного автоматного часу й нумерують натуральними числами, починаючи з одиниці. Значення вхідних і вихідних сигналів та значення станів автомата можуть змінюватися тільки в моменти автоматного часу t = 1, 2, ….

Якщо позначимо через

x(t) X, y(t) Y, a(t) U

значення вхідного й вихідного сигналів і стану автомата в момент автоматного часу t, то робота автомата A описуватиметься співвідношеннями

a(t + 1) = δ(a(t), x(t)), y(t) = λ(a(t), x(t)). (5.1)

Співвідношення (5.1) називають канонічними рівняннями автомата A.

Перше із канонічних рівнянь можна прочитати так: стан автомата A в будь-який момент автоматного часу t + 1 однозначно визначається сигналом, поданим на вхід автомата, і станом автомата A в попередній момент автоматного часу. При цьому кажемо, що автомат A переходить зі стану a(t) у стан a(t + 1).

У математичній моделі автомата можна вважати, що такий перехід відбувається миттєво (стрибкоподібно). За фізичної ін-

201

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

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

Якщо у автоматі A виділено стан, у якому автомат A перебуває в момент автоматного часу t = 1, то цей стан називають початко вим (зазвичай початковим станом уважають a1), а автомат A називають ініціальним і позначають A/a1. Надалі не вказуватимемо явно залежність змінних і результатів функцій переходів і виходів від автоматного часу t, крім тих випадків, коли це потрібно.

Для розв'язання задач теорії автоматів зручно використовувати різні способи (методи) задання автоматів. Опишемо два найпоширеніші. У цих методах істотним є те, що функції δ та λ автомата A мають скінченні області визначення.

Табличний спосіб. Функції δ і λ можна задавати за допомогою двох таблиць, які називають відповідно

дів і таблицею виходів автомата A. Загальна структура обох таблиць однакова: рядки таблиць позначено вхідними сигналами x1, x2, …, xm, а стовпчики – станами a1, a2, …, as. На перетині i-го рядка та j-го стовпчика в таблиці переходів записують стан δ(aj, xi), а в таблиці виходів – вихідний сигнал λ(aj, xi). Іноді для задання автомата використовують одну

реходів/виходів, у якій на перетині i-го рядка та j-го стовпчика

записують відповідну пару ak /yl, де ak = δ(aj, xi) та yl = λ(aj, xi). Графічний спосіб задання автомата за допомогою орієнтова-

ного мультиграфа називають графом, або діаграмою автомата

(автоматним графом, автоматною діаграмою). Вершини графа позначають символами станів автомата A. Якщо δ(ai, xk) = aj та λ(ai, xk) = yl , то в графі автомата проводять орієнтовану дугу (або стрілку) з вершини ai у вершину aj й позначають її символами xk/yl. Задання автомата за допомогою графа особливо наочне, якщо кількість його станів порівняно невелика.

202

Зрозуміло, що досить легко можна перейти від одного способу задання до іншого.

Автомат A називають детермінованим, якщо функції δ і λ всюди визначені, і недетермінованим, якщо δ і λ – усюди визначені відповідності між U × X і U та U × X та Y, відповідно, але вони не задовольняють умову функціональності. Автомат A називають частковим, якщо функції δ і λ не є всюди визначеними.

Приклад 5.1.

1. Розглянемо автомат D, який регулює дорожній рух на перехресті вулиць В і П.

В автомат дорожнього руху D з періодом одна хвилина надходить тактовий сигнал Г генератора синхроімпульсів, що послідовно перемикає сигнали світлофора С, дозволяючи транспорту рух відповідно вулицями В і П (рис. 5.1, а). Крім світлофора є також кнопка виклику К, за допомогою якої пішохід може надіслати автомату запит З на призупинення руху на перехресті. При надходженні запиту З і по завершенні поточного інтервалу часу в одну хвилину автомат перериває генерування послідовності сигналів В і П на дві хвилини, сигналом Д запалює транспарант, що дозволяє перехід пішоходам, а по вичерпанні двох хвилин формує сигнал скидання СС, повертаючи автомат до відновлення формування послідовності сигналів В та П. Таким чином, автомат D виробляє вихідні сигнали В, П, Д і СС для дозволу руху транспорту по вулицях В і П, дозволу переходу пішоходам та скидання кнопки виклику. Роботу автомата D ілюструє часова діаграма на рис. 5.1, б.

Таблиці переходів і виходів автомата дорожнього руху мають такий вигляд:

203

Тут використано позначення:

x1 = Г, x2 = З & Г, y1 = В, y2 = П, y3 = Д, y4 = Д & СС):

Граф автомата дорожнього руху подано на рис. 5.2.

Рис. 5.2

2. Побудуємо автомат S, який описує алгоритм функціонування послідовного двійкового суматора. На вхід автомата надходять пари розрядів двійкових чисел, що додаються, починаючи з молодших розрядів. На виході автомата має з'являтися розряд результату додавання. Потрібно також фіксувати й ураховувати ситуацію наявності чи відсутності перенесення в наступний розряд. Ці дві ситуації відображають два стани автомата S: початковому стану a1 відповідає ситуація немає перенесення, а стану a2 – ситуація є перенесення.

Вхідні сигнали x0 = (0, 0), x1 = (0, 1), x2 = (1, 0) і x3 = (1, 1) за-

дають чотири можливі комбінації розрядів, що додаються. Граф автомата S подано на рис. 5.3.

3. Побудуємо суміщену таблицю переходів/виходів автомата A, на виході якого з'являється сигнал 1 тоді й лише тоді, коли на його вхід було подано послідовність символів, що відповідає ідентифікатору якоїсь мови програмування; в іншому разі вихідним сигналом є 0. Вхідні сигнали автомата A: x1 – літера, x2 – цифра, x3 – будь-який інший символ.

П – початковий стан автомата A. Автомат перебуває у стані T, коли на його вхід подається послідовність символів, що відповідає ідентифікатору, в іншому разі він перебуває у стані H.

4. Побудувати автомат-пошуковець S для X = Y = {0, 1}, на виході якого з'являється сигнал 1 тоді й лише тоді, коли чотири останні вхідні сигнали – це 0110.

Позначимо через 0 стан, що відповідає очікуванню бажаної (шуканої) четвірки символів, через 1 – стан, що фіксує появу на вході автомата першого 0 четвірки, через 2 – стан, що відповідає появі пари 01, через 3 – стан, що відповідає появі 011, і через 4 – стан, у який автомат переходить, коли останніми вхідними сигналами є 0110. Суміщену таблицю переходів/виходів автомата-

5. Побудувати таблиці переходів і виходів, граф автомата P, що за допомогою своїх станів запам'ятовує два останні символи (двійкові розряди), які було подано на його вхід. Вихідним сигналом є останній символ, що "забувається".

Для зручності стани автомата P позначено чотирма можливими варіантами значень двох останніх символів (двійкових розрядів) вхідного слова, тобто автомат P перебуває в стані ab, якщо двома останніми вхідними символами були ab, a, b {0, 1}. ◄

205