Способи опису роботи автоматів

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

Існують декілька способів завдання кінцевих автоматів, наприклад:

- табличний (матриці переходів і виходів);

- графічний (за допомогою графів);

- аналітичний (за допомогою формул).

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

Табличний. Опис роботи автомата Мілі таблицями переходів і виходів ілюструється таблицями 1.1 і 1.2. Рядки цих таблиць відповідають вхідним сигналам, а стовпці - станам, причому крайній лівий стовпець станів позначений початковим станом q₁.

На перетині стовпця d(q_m, x_F) і рядки x_F в таблиці переходів ставиться стан q _s = d(q_m, x_F), в який автомат переходить із стану q_m під дією сигналу x_F, а в таблиці виходів - відповідний цьому переходу вихідний сигнал y_g = l(q_m, x_F).

Таблиця 1. 1 - Загальний вигляд таблиці переходів автомата Мілі

	q1	…	qm
X1	d(q1, x1)	…	d(qm, x1)
…	…	…	…
XF	d(q1, xF)	…	d(qm, xF)

Таблиця 1.2 - Загальний вигляд таблиці виходів автомата Мілі

	q1	…	qm
X1	l(q1, x1)	…	l(qm, x1)
…	…	…	…
XF	l(q1, xF)	…	l(qm, xF)

Приклад табличного способу завдання повністю визначеного автомата Мілі S₁ з трьома станами, двома вхідними і двома вихідними сигналами приведений в таблицях 1.3 і 1.4.

Таблиця 1. 3 - Таблиця переходів автомата Мілі S₁

	q1	q2	q3
X1	q3	q1	q1
X2	q1	q3	q2

Таблиця 1. 4 - Таблиця виходів автомата Мілі S₁

	q1	q2	q3
X1	y1	y1	y2
X2	y1	y2	y1

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

Приклад об’єднаної таблиці автомата Мілі S₁ з трьома станами, двома вхідними і двома вихідними сигналами приведений в таблиці 1.5.

Таблиця 1.5 – Об’єднана таблиця автомата Мілі S₁

	q1	q2	q3
X1	q3 y1	q1 y1	q1 y2
X2	q1 y1	q3 y2	q2 y1

Для часткових автоматів, у яких функції d або l визначені не для усіх пар (q_m, ,x_F) Î Q´X, на місці невизначених станів і вихідних сигналів ставиться прочерк (частковий автомат S₂ заданий таблицями 1.6 і 1.7).

Таблиця 1. 6 - Таблиця переходів часткового автомата Мілі S₂

	q1	q2	q3	q4
X1	q2	q3	q4	-
X2	q3	-	q2	q2

Таблиця 1.7 - Таблиця виходів часткового автомата Мілі S₂

	q1	q2	q3	q4
X1	y1	y3	y3	-
X2	y2	-	y1	y2

Оскільки в автоматі Мура вихідний сигнал залежить, тільки від стану, автомат Мура задається однією відміченою таблицею переходів (таблиця 1.8), в якій кожному її стовпцю приписаний, окрім стану q _m, ще і вихідний сигнал y_m = l (q _m), відповідний цьому стану. Зна­чення виходів автомата встановлюється окремим рядком над заго­ловками кожного стовпця.

Приклад табличного опису автомата Мура S₃ ілюструється таблицею 1. 9.

Таблиця 1.8 - Загальний вигляд відміченої таблиці переходів автомата Мура

	l(q1)	…	l(qm)
	q1	…	qm
X1	d(q1, x1)	…	d(qm, x1)
…	…	…	…
XF	d(q1, xF)	…	d(qm, xF)

Таблиця 1. 9 - Відмічена таблиця переходів автомата Мура S₃

	y1	y1	y3	y2	y3
	q1	q2	q3	q4	q5
X1	q2	q5	q5	q3	q3
X2	q4	q2	q2	q1	q1

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

Дві вершини графа автомата q _m і q _s (початковий стан і стан переходу) з'єднуються дугою, спрямованою від q m до q _s, якщо в автоматі є перехід з q _m в q _s, тобто якщо q _s = d (q_m, х_f) при деякому х_f Î X. Дузі (q _m, q _s) графа автомата приписується вхідний сигнал x_f і вихідний сигнал y_g = l (q _m, x_f), якщо він визначений, інакше ставиться прочерк. Якщо перехід автомата із стану q_m в стан q _s відбувається під дією декількох вхідних сигналів, то дузі (q _m q _s) приписуються усі ці вхідні та відповідні вихідні сигнали. При описі автомата Мура у вигляді графа вихідний сигнал y_g = l (q _m) записується усередині вершини або поряд з нею. На рис.1.4, 1.5 і 1.6 приведені задані раніше таблицями графи автоматів S₁, S₂, S₃.

Рисунок 1.4 – Граф автомата Мілі S₁

Рисунок 1.5 - Граф автомата Мілі S₂

Рисунок 1.6 - Граф автомата Мілі S₃

Граф-схеми широко використовують як в аналізі, так і в син­тезі автоматів, а також під час переходу від словесного до фор­малізованого їх опису.

За допомогою таблиць переходів та виходів, як і за допомо­гою граф-схеми, завжди можна знайти вихідну реакцію автома­та на будь-яке вхідне слово, що належить множині X.

Для опису С- автоматів також використовується табличний і графічний методи. Наприклад, у першому випадку таблиця переходів (таблиця. 1.10) аналогічна таблиці переходів автомата Мілі, а в таблиці виходів кожен стан відмічений відповідним йому сигналом типу 2 (таблиця. 1.11). При завданні С-автомата у вигляді графа (сигнали типу 1 приписуватимемо дугам графа поряд з вхідними сигналами, а сигнали типу 2 – вершинам - станам, яким вони відповідають (рис. 1.7).

Таблиця 1.10 - Таблиця переходів С- автомата

	q1	q2	q3	q4	q5	q6
X1	q6	q6	q4	q3	q4	q1
X2	q4	q3	q5	q5	q5	q2

Таблиця 1.11 - Відмічена таблиця виходів С- автомата

	U1	U1	U3	U3	U2	U2
	q1	q2	q3	q4	q5	q6
X1	W1	W1	W2	W1	W2	W2
X2	W2	W1	W1	W2	W1	W1

Рисунок 1.7 - Граф C- автомата

Матричний. Матриця з'єднань автомата є квадратна матриця С =|| c_ms ||, рядки якої відповідають початковим станам, а стовпці - станам переходу. Елемент с_ms = x_f / y_g, що стоїть на перетині m -го рядка і s -го стовпця, у разі автомата Мілі відповідає вхідному сигналу x_f, що викликає перехід із стану q_m в стан q_s, і вихідному сигналу y_g, що видається на цьому переході. Для автомата Мілі S₁ матриця C має вигляд

Якщо перехід з q_m в q_s відбувається під дією декількох сигналів, елемент с_ms є множиною пар (вхід/вихід) для цього переходу, сполучених знаком диз'юнкції. Для моделі Мура елемент c_ms дорівнює множині вхідних сигналів на переході (q_m, q_s) а вихід описується вектором виходів m -а компонента якого є вихідний сигнал, що відмічає стан q_m.

,

Для автомата Мура S₃

,

Матричне представлення кінцевих автоматів при малому числі внутрішніх станів може бути виконано і в декілька іншій формі. Матриця при цьому перетворюється у вертикально розвернуту таблицю, перші два стовпця які відповідно містять поточне і наступне внутрішні стани. У третьому стовпці містяться умови переходу, записаного в рядку. Приклад такої таблиці (таблиця 1.12), отриманої з матриці для автомата S₁, приводиться нижче.

Таблиця 1.12- Розвернута таблиця

qn(t)	qn(t+1)	Умови
q1	q1
q1	q2	-
q1	q3
q2	q1
q2	q2	-
q2	q3
q3	q1
q3	q2
q3	q3	-

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

qn(t)	qn(t+1)	Умови
q1	q1
q1	q2	-
q1	q3
q2	q1
q2	q2	-
q2	q3
q3	q1
q3	q2
q3	q3	-

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

Отримання алгоритму функціонування автомата не є формалізованим процесом. Для цього необхідно чітко представляти cnoci6 пе­ретворення інформації.

Для опису алгоритму функціонування цифрового автомату зручно використовувати графічні схеми алгоритмів (ГСА) та логічні (лінійні) схеми алгоритмів (JICA).

ГСА складається з вершин чотирьох типів (рис. 1.8):

1. Початково-операційна вершина.

2. Кінцева - операційна вершина.

3. Операційна вершина, що описує вихідний стан Y.

4. Логічна умова, що аналізує логічний сигнал X.

Будь-яка вершина ГСА, окрім вершини «Початок» має по одному входу. Вершина «Початок» входів не має. Вершина «Початок» і будь-яка операторна вершина мають по одному виходу. Вершина «Кінець» виходів не має. Будь-яка умовна вершина має два виходи, які помічені символами «Так» і «Ні», або «1» і «0» відповідно.

а) б) в) г)

Рисунок 1.8 - Умовні позначення вершин у ГСА

Правила складання ГСА:

- ГСА починається з вершини «Початок» i закінчується вершиною «Кінець».

- Входи і виходи вершин з'єднуються одна з одною за допомогою дуг, спрямованих від виходу до входу.

- Букви Y_l вихідного алфавіту (вихідні сигнали, оператори) записують в оператори вершини, а букви Х вхідного алгоритму (вхідні сигнали, логічні умови) розміщують у логічні (умовні) вер­шини.

- Кожен вихід сполучений тільки з одним входом.

- Будь-який вхід з'єднується, принаймні, з одним виходом.

- Будь-яка вершина ГСА лежить хоч би на одному шляху від вершини "Початок" до вершини "Кінець".

- Один з виходів умовної вершини може з'єднуватися з її входом, що неприпустимо для операторної вершини.

- Дозволяється в різних умовних вершинах записувати однакові логічні умови.

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

Після створення ГСА процес побудови графа автомата і визна­чення алфавіту внутрішніх станів можна формалізувати. У зв'язку з цим ГСА, як і граф, можна вважати формальним описом абстракт­ного автомата. Приклад ГСА наведено на рисунку 1.9.

Рисунок 1.9 - Графічна схема алгоритму (ГСА)

За допомогою ЛСА алгоритми записують у вигляді кінцевої стрічки, що складається з символів операторів, логічних умов і верхніх та нижніх стрілок, яким приписані натуральні числа (, , і = 1, 2,...).

ЛСА задовольняють наступним умовам:

1. Містять один початковий (Y_н) і один кінцевий оператор (Y_к).

2. Перед оператором Y_H і після оператора Y_K стрілок бути не повинно.

3. Услід за кожною логічною умовою завжди стоїть верхня стрілка.

4. Не існує двох однакових (з однаковими цифрами) нижніх стрілок.

5. Для кожної нижньої стрілки має бути принаймні одна верхня стрілка.

6. Для кожної верхньої стрілки має бути точно одна нижня стрілка.

Приклад

Y_H x₁ Y₁ x₂ Y₂ Y₃ Y₄ Y_K

Ця JICA має оператори початку і кінця (Y_H і Y_K), чотири оператори Y₁-Y₄ і дві логічні умови. Початковому оператору відповідає деякий початковий стан дискретного пристрою, при якому ніякі мікрооперації не виконуються. Якщо в початковому стані на вхід х₁ пристрою прийде сигнал, рівний одиниці (x₁ = 1), то пристрій перейде в новий стан, в якому виконується оператор Y ₁ - перший справа після логічної умови х₁. Якщо х =0, то виходимо по верхній стрілці і шукаємо нижню стрілку з тією ж цифрою . Після неї стоїть логічна умова х₂ із стрілкою , а за нею – оператори Y₂ Y₃ . За стрілкою стоїть оператор Y₄ . Якщо х1= 0 та х2=1, то пристрій із начального стану переходить в деякий новий стан з виконанням оператора Y ₂ (x₁ … x₂ … Y₂), а якщо х 1= 0 і х2 = 0, то виконується оператор Y₄ (x₁ ... х₂ ... Y₄). Потім виконання оператора Y₂ незалежно від значень логічних умов виконується той оператор, що стоїть праворуч від Y₂ тобто Y₃, а потім Y₄ і т. д. Наведена JICA описує роботу пристрою точно так, як і ГСА на рис. 1.10.

X1

X2

YH

Y1

Y3

Y2

Y4

YK

Рисунок 1.10 - Графічна схема алгоритму

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

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

Таблиця 1.13- Стрічка цифрового автомата

Особливість такої стрічки полягає в тому, що для будь-якої пари сусідніх тактів і та (i +1) можна виділити четвірку символів (виділена у табл. 1.13 жирною лінією), яка показує, в який стан перейде цифровий автомат в (i +1)-му такті і який вихідний сигнал буде сформований під дією вхідного сигналу.

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

На рис. 1.11 наведено приклад дерева переходів, що відповідає табл. 1.13.

Рисунок 1.11 – Дерево переходів