Абстрактні автомати

Математичну модель дискретного пристрою називають абстрактним автоматом згідно наступному означенню.

Означення 4.1. Абстрактний автомат – це шестикомпонентний кортеж A=(Z,W,Q,δ,λ,q₀), де:

Z={z₁,z₂,…,z_f,…,z_F} – множина вхідних сигналів (символів вхідного алфавіту);

W={w₁,w₂,…,w_g,…,w_G} – множина вихідних сигналів (вихідний алфавіт);

– множина станів (алфавіт станів);

δ: Q×Z→Q – функція переходів, що деяким парам (q_m,z_f) “стан – вхідний сигнал” ставить у відповідність певні стани автомата q_s=(q_m,z_f), ;

λ: Q×Z→W – функція виходів, що парам (q_m,z_f) ставить у відповідність вихідні сигнали автомата w_s=λ(q_m,z_f), w_sÎW;

– початковий стан автомата.

Абстрактний автомат має один вхідний і один вихідний канали (рис. 4.4).

Абстрактний автомат, в якому виділено один із станів q₀, називається ініціальним. Це стан, з якого автомат починає роботу і в який він переходить по її закінченні. В деяких задачах такий початковий стан не є необхідним, тоді абстрактний автомат описується п’ятикомпонентним кортежом A=(Z,W,Q,δ,λ).

Означення 4.2. Автомат A=(Z,W,Q,δ,λ,q₀) називається скінченним, якщо алфавіти Z і W входу і виходу та множина Q його станів скінченні.

Надалі ми будемо мати справу тільки з скінченними автоматами.

Функціонування автомата розглядається в дискретні моменти автоматного часу t₁, t₂, …, t_i, які називаються тактовими моментами. Припускається, что поведінка автомата не залежить від інтервала часу між t_i і t_i+1. Таким чином, фактично змінною є не сам час, а порядкові номери тактових моментів t=0, 1, 2, …, i,…. Реальна же тривалість тактів може бути довільною. Приймається також допущення, що перехід автомата із одного стану в наступний здійснюється стрибково, тобто миттєво. В реальних же автоматах завжди має місце кінцева тривалість перехідних процесів.

Процес функціонування абстрактного автомата можна уявити наступним чином. У кожен момент автомат перебуває в деякому стані , а в початковий – завжди в початковому стані . Сприймаючи в момент на вхідному каналі деякий символ вхідного алфавіту z(t)=z_f Z, автомат видає на вихідному каналі в цей самий момент символ вихідного алфавіту w(t)=w_g W і перемикається в новий стан , який зберігатиметься протягом наступного такту часу. Вихідний сигнал і наступний стан визначають функції виходів λ і переходів δ:

, (4.1)

. (4.2)

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

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

Виразам (4.1) та (4.2) відповідає автомат, вихідний сигнал якого залежить від його стану і від сигналу на його вході. Це автомат Мілі.

Автомат, в якого вихідний сигнал w(t) у такті t явно не залежить від вхідного z(t), а тільки від його внутрішнього стану, нази­вають автоматом Мура. Функціонування такого автомата описують вирази (4.3) та (4.4). , (4.3) . (4.4)

Означення 4.3. Якщо символи вхідного і вихідного алфавітів Z і W кодуються цифрами, то такий автомат називається цифровим.

Будь-який реальний автомат можна спроектувати за моделлю Мілі або Мура.