Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лабораторна робота №7.
Синтез скінченого автомата
1. Основні поняття теорії скінченних автоматів
Скінченним автоматом називається система S={A, Q, V, d, l}, у якої A={a1,…,am},Q={q1,…qn},V={v1,…,vk}- скінченні множини (алфавіти); a d: Q x A Q і l: Q x A V - функції, визначені на цих множинах. А називається вхідним алфавітом, V - вихідним алфавітом, Q - алфавітом стану; d - функцією переходів, l - функцією виходів. Якщо, крім того, в автоматі S виділено один стан, який називається початковим (будемо вважати, що цей стан q0), то отриманий автомат називається ініціальним і позначається ( S, q0 ) ; таким чином, по неініціальному автомату з n станами можна n різноманітними способами визначити ініціальний автомат.
Оскільки функції d і l визначені на скінченних множинах, їх можна задавати таблицями. Звичайно дві таблиці зводяться в одну таблицю d і l , яка називається таблицею переходів-виходів автомата або автоматною таблицею.
Приклад. Табл. 3.5 задає функції переходів і виходів для автомата з алфавітами A = { a1, a2, a3}, Q = {q1, q2, q3, q4}, V = {v1, v2}.
Таблиця 3.5.
Табличне завдання скінченного автомата
|
A1 |
a2 |
a3 |
|
|
q1 |
q3 / v1 |
q3 / v2 |
q2 / v1 |
|
q2 |
q4 / v1 |
q1 / v1 |
q1 / v1 |
|
q3 |
q2 / v1 |
q3 / v1 |
q3 / v2 |
|
q4 |
q4 / v1 |
q2 / v1 |
q1 / v2 |
Ще один поширений і наочний спосіб завдання автоматів - орієнтований мультиграф, називаний графом переходів або діаграмою переходів. Вершини графа відповідають станам; якщо d (qi, aj) = qk і l (qi, aj)= vl, то з qi у qk йде ребро, на якому написані aj і vl . Граф переходів для таблиці 3.5 зображений на рис. 3.7. Кратні ребра не обов'язкові; наприклад два ребра з q2 у q1 можна замінити одним, на якому будуть написані обидві пари a3/v1 і a2/v1 . Для будь-якого графа переходів у кожній вершині qi виконані такі умови, що називаються умовами коректності:
1) для будь-якої вхідної букви ai є ребро, що виходить із qi, на якому написане aj (умовна повнота);
2) будь-яка буква aj зустрічається тільки на одному ребрі, що виходить із qi (умова несуперечності або детермінованості).
Для даного автомата S його функції dS і lS можуть бути визначені не тільки на множині А усіх вихідних букв, але і на множині А* усіх вхідних слів. Для будь-якого вхідного слова a = (aj1, aj2, ..., ajk); d( qi, aj1, aj2, …, ajk) =
= d ( d ( ...d ( qi, aj1), aj2), … , ajk-1), ajk).
Іншим способом це традиційне визначення можна представити так:
1) d ( qi , aj ) задається автоматною таблицею S;
2) для будь-якого слова a А* і будь-якої букви аj
d( qi, aaj ) = d ( d( qi, a ), aj).
Рис. 3.7. Граф скінченного автомата
Тут і надалі символи станів для формування коротких позначень будуть замінятися їхніми індексами.
За допомогою розширеної функції d визначається (індуктивно) розширена функція l .
l(qi, aaj) = l ( d ( qj , a), aj).
Зафіксуємо в автоматі S початковий стан q1, і кожному вхідному слову a = аj1, аj2, …, аjk поставимо у відповідність слово w у вихідному алфавіті
w = l ( q1, aj1) l ( q1,aj1aj2 ) ... l ( q1,aj1,…,ajk ).
Ця відповідність, що відображає вхідні слова у вихідні, називається автоматним відображенням, а також автоматним оператором. Якщо результатом застосування оператора до слова a є вихідне слово w, то це будемо позначати відповідно S (q1, a) = w або S( a ) = w . Число букв у слові a, як звичайно, є довжиною a і позначається a або l().
Автоматне відображення має такі властивості:
Остання властивість відбиває той факт, що автоматні оператори - це оператори, які, переробляючи слово зліва праворуч, не «заглядають вперед». При цьому i - а буква вихідного слова залежить тільки від перших i - букв вихідного слова.
Зазначені властивості були б достатніми умовами автоматного відображення, якби мова йшла про нескінченні автомати. Для скінченних автоматів цих умов недостатньо при реалізації для довільних вхідних і вихідних алфавітів.
2. Абстрактна і структурна теорії скінченних автоматів
Під автоматом розуміється пристрій, що самостійно виконує всі операції. Формальний опис автомата називають його логічною структурою. Властивості і методи перетворення логічних структур вивчає теорія кінцевих автоматів, яка підрозділяється на абстрактну і структурну. Абстрактна теорія не торкається структури самого автомата, обмежуючись лише розглядом переходів, що виконуються автоматом при зміні вхідних сигналів, які видаються автоматом у кожному стані. Структурна теорія вивчає способи побудови автоматів, їхню структуру, способи кодування вхідних і вихідних сигналів.
Автомат називається комбінаційним, якщо для будь-якого вхідного символу а і будь-яких станів qi і qj (qi, a)= (qj, a), інакше кажучи, якщо вихідний символ не залежить від стану і повністю визначається поточним вхідним символом. У такому автоматі всі стани еквівалентні, і, отже, мінімальний комбінаційний автомат має один стан. Функція переходів у ньому вироджена, і його поведінка однозначно задається функцією виходів з одним із аргументів: (ai)=vi.
Усі автомати можна розділити на синхронні й асинхронні. Відомі дві моделі синхронних елементарних автоматів: модель Мура і модель Милі, що одержали назви за іменами вчених, які розробили відповідні розділи теорії автоматів. Моделлю Мура називається автомат, що описується рівняннями
q(t) = [x(t-1); q(t-1)]; v(t)= [q(t)],
де q(t), q(t-1) - стани автомата в моменти часу t і t-1; x(t-1), v(t) - вхідний і вихідний сигнали автомата в моменти часу t і t-1.
Для моделі Милі справедливі співвідношення
q(t) = [x(t-1); q(t-1)];
v(t)= [x(t); q(t)].
Існує декілька способів представлення скінченних автоматів, основними з яких є графічний, таблично-матричний, аналітичний із використанням секвенціальних рівнянь. Нехай необхідно синтезувати автомат, що дозволяє роботу деякого пристрою при наявності одиничних сигналів на входах Х1, Х2 , причому для вмикання пристрою необхідно виконати умову появи сигналу на вході Х1 раніш ніж на вході Х2. При графічному способі опису даний автомат можна представити у вигляді спрямованого графа (рис. 3.8 і 3.9), вершинами якого є стан автомата, а ребрами - комбінації вихідних сигналів.
Як очевидно з графа, комбінація (01) викликає перехід автомата з деякого стана S0 у стан S1, що відповідає появі одиничного сигналу на виході У, автомат може перейти тільки зі стана S1 за умови надходження комбінації вхідних сигналів Х1, Х2 (11). Даний граф відповідає представленню автомата моделлю Мура, тому що вихідний сигнал (зазначений у вузлах графа) цілком визначається внутрішнім станом автомата і не залежить від комбінації сигналів на вході. При завдаванні автомата моделлю Милі його вихідний сигнал указується над кожним ребром графа ( рис. 3.9), оскількі залежить не тільки від внутрішнього стану автомата, але і від комбінації сигналів, що надходять на вхід автомата в даний момент часу.
Рис. 3.8. Граф автомата Мура
Рис. 3.9. Граф автомата Милі
Замість побудови графа всю необхідну інформацію про роботу можна зводити в спеціальні автоматні таблиці: таблицю переходів і таблицю виходів. Представлення автомата за допомогою таблиць показано в табл. 3.6. - 3.9.
Таблиця 3.6.
Таблиця переходів автомата Мура
|
Стани |
Вхідні сигнали |
|||
|
00 |
01 |
11 |
10 |
|
|
g0 |
g0 |
g0 |
g1 |
G0 |
|
g1 |
g0 |
g0 |
g1 |
G2 |
|
g2 |
g0 |
g0 |
g1 |
G2 |
Таблиця 3.7.
Таблиця виходів автомата Мура
|
Стани |
g0 |
g1 |
g2 |
|
Вихідні сигнали |
0 |
0 |
1 |
Таблиця 3.8
Таблиця переходів автомата Милі
|
Стани |
Вхідні сигнали |
|||
|
00 |
01 |
11 |
10 |
|
|
g0 |
G0 |
g0 |
G1 |
g0 |
|
g1 |
g0 |
g0 |
G1 |
g1 |
Таблиця 3.9
Таблиця виходів автомата Милі
|
Стани |
Выхідні сигнали |
|||
|
00 |
01 |
11 |
10 |
|
|
g0 |
0 |
0 |
0 |
0 |
|
g1 |
0 |
0 |
0 |
1 |
На перетинанні рядків і стовпчиків автоматних таблиць указуються внутрішні стани, в які переходить автомат під дією вхідних сигналів і вихідні сигнали, що він при цьому видає. Обидві розглянутих форми задавання автоматів побудовані для того самого приклада автоматів Мура і Милі.
3. Приклад синтезу скінченного автомата
Нехай скінченний автомат заданий сполученою таблицею переходів- виходів.
Таблиця переходів-виходів скінченного автомата.
x(n) (стан / вихід)
s(m) 0 1 2 3
|
0 |
2/0 |
2/0 |
0/0 |
0/1 |
|
1 |
1/1 |
1/0 |
0/1 |
1/1 |
|
2 |
1/0 |
0/1 |
2/1 |
0/0 |
Таблиця 3.11.
Проміжна таблиця
|
Входи |
x(n) |
000 111 222 333 |
|
Поточні стани |
s(n) |
012 012 012 012 |
|
Наступні стани |
s(n+1) |
211 210 002 010 |
|
Виходи |
y(n) |
010 001 011 110 |
Замінюючи десяткові числа на двійкові, одержимо таблицю істинності, в якій значення x(n), s(n), s(n+1), y(n) подані в двійковому коді.
Таблиця 3.12.
Таблиця істинності кінцевого автомата
|
x(n) |
s(n) |
s(n+1) |
y(n) |
|||
|
x1(n) |
x2(n) |
s1(n) |
s2(n) |
s1(n+1) |
s2(n+1) |
|
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
0 |
1 |
0 |
1 |
1 |
|
0 |
0 |
1 |
0 |
0 |
1 |
0 |
|
0 |
0 |
* |
* |
* |
* |
* |
|
0 |
1 |
0 |
0 |
1 |
0 |
0 |
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
0 |
0 |
1 |
|
0 |
1 |
* |
* |
* |
* |
* |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
1 |
0 |
0 |
1 |
|
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
1 |
0 |
* |
* |
* |
* |
* |
|
1 |
1 |
0 |
0 |
0 |
0 |
1 |
|
1 |
1 |
0 |
1 |
0 |
1 |
1 |
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
1 |
* |
* |
* |
* |
* |
Граф скінченного автомата буде мати вигляд, показаний на рис. 3.13.
0/1 1/0 3/1
2/1 1
0 1/1 3/0 0/0
2/0 3/1
0/0 0/1 2 2/1
Рис. 3.13. Граф синтезованого скінченного автомата
Вихідні функції для синтезу автомата за табл. 3.12 буде мати вигляд
s1(n+1) = x1(n)x2(n)s1(n)s2(n) x1(n) x2(n)s1(n)s2(n)
x1(n)x2(n)s1(n)s2(n);
s2(n+1) = x1(n)x2(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n)
x1(n)x2(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n);
y(n) = x1(n)x2(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n)
x1(n)x2(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n)
x1(n)x2(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n).
Мінімізуємо дані функції за допомогою карт Карно.
Для s1(n+1).
x1(n)x2(n)
s1(n)s2(n) 00 01 11 10
|
00 |
1 |
1 |
||
|
01 |
||||
|
11 |
||||
|
10 |
1 |
Для s2(n+1).
x1(n)x2(n)
s1(n)s2(n) 00 01 11 10
|
00 |
||||
|
01 |
1 |
1 |
1 |
|
|
11 |
||||
|
10 |
1 |
Для y(n).
x1(n)x2(n)
s1(n)s2(n) 00 01 11 10
|
00 |
1 |
|||
|
01 |
1 |
1 |
1 |
|
|
11 |
||||
|
10 |
1 |
1 |
Результати мінімізації представимо у вигляді
s1(n+1) = x1(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n);
s2(n+1) = x1(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n)
x1(n)x2(n)s1(n)s2(n);
y(n)=x2(n)s1(n)s2(n) x1(n)x2(n)s1(n) x1(n)x2(n)s1(n)s2(n)
x1(n)x2(n)s1(n)s2(n).
Структура автомата в загальному вигляді подана на рис. 3.14.
x1(n) Комб. y(n)
x2(n) схема s1(n+1)
s1(n)
s2(n) s2(n+1)
П1
Рис. 3.14. Структурна схема скінченного автомата
Комбінаційна схема автомата і її зв'язок з елементами пам'яті показані на рис. 3.15.
x1(n) x2(n) s1(n) s2(n) s2(n)s1(n)x2(n)x1(n) KC
x1(n) 1 &
x2(n)
1 1 y(n)
& 1
&
1
&
s2
& 1 (n+1)
&
& s1
(n+1)
1
&
П2
s2(n)
П1 Пам'ять
s1(n)
Рис. 3.15. Схема скінченного автомата
Таким чином, синтезований скінченний автомат містить 4 елементи "НЕ", три елементи "АБО", дев'ять елементів "І" і два елементи пам'яті.
Скінченний автомат являє собою точну з функціональної точки зору модель дискретного обчислювального або керуючого пристрою. Вхідна буква - це вхідний сигнал (точніше - комбінація сигналів на усіх входах пристрою), вхідне слово - послідовність вхідних сигналів, що надходять в автомат у дискретні моменти часу.
Вихідне слово - послідовність вихідних сигналів, що видаються автоматом. Стани автомата - це комбінації станів елементів пристрою, що запам'ятовують.
Проте навіть із прикладної точки зору інтерпретація автомата як пристрою не є універсальною. Відомо, що довільний обчислювальний пристрій можна реалізувати як апаратно (у вигляді пристрою), так і програмно (у вигляді програми для ЕОМ). Це призводить до більш загального тлумачення автоматів як алгоритмів із скінченною пам'яттю, багато властивостей яких можна досліджувати иезалежно від способу їхньої реалізації.