1 Скінченні автомати. Методи задання автоматів Лекція 11 Теорія автоматів

x2, ..., xm} і Y = {y1, y2, ..., yn}

– дві довільні множини елементів, які називатимемо алфавітами, а їх елементи – літерами алфавітів. Скінченну впорядковану послідовність літер називатимемо словом у заданому алфавіті. Позначимо через (X) і (Y) множини всіх слів в алфавітах X та Y, відповідно. У такому випадку перетворення дискретної інформації можна задати як відображення f множини слів (X) у множину слів (Y).

Y – вхідним і вихідним алфавітами оператора f. Кожному вхідному

слову p = хі1, хі2, …, хіk відображення f зіставляє слово на виході r = уі1, уі2, …, уіk. Тому (p(X))(r(Y))[r = f(p)]. У цьому випадку f є функцією, область визначення якої – (X), а область значень – (Y).

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

Алфавітне відображення

довільного числа станів автомата, що відрізняються;
миттєве здійснення переходу із одного

стану автомата в інший;
перехід із одного стану в інший не раніше, ніж за деякий проміжок часу  (>0 – інтервал дискретності);
число різноманітних вхідних і вихідних літер (сигналів) є скінченним;
вхідні літери – причина переходу автомата з одного стану до іншого, а вихідні – реакція автомата на вхідні літери, які належать до моментів часу, що визначаються відповідними переходами автомата.

Інтуїтивне поняття автомата (1)

у дискретному часі t, який набуває значень t =

0, 1, 2, ... . На кожний вхідний сигнал x(t) (t>0) автомат реагує вихідним сигналом y(t).

Розрізнюють два види автоматів: синхронні та асинхронні (перехід з одних станів до інших здійснюється через нерівні проміжки часу).

Зупинимось на законах функціонування автоматів.

Інтуїтивне поняття автомата (2)

визначається попереднім станом q(t–1) і вхідним сигналом x(t). Тому можна

записати

q(t) = (q(t–1), x(t)), або :QXQ,

де  – функція, що визначає наступні стани автомата, позначається (q, x) і називається функцією переходів, Q – алфавіт станів автомата, X – алфавіт вхідних сигналів.

Функція переходів автомата

вхідного сигналу x(t). Але щодо моменту часу t переходу автомата

зі стану q(t–1) до стану q(t) вихідний сигнал y(t) може з'явитися раніше або пізніше від цього моменту часу. Тому справедливими є такі вирази

y(t) = (q(t–1), x(t)), (1)
y(t) = (q(t), x(t)), (2)

де (q, x) – функція виходів звичайна (1) або зсунута (2).

Функція виходів звичайна та зсунута (1)

Функція виходів звичайна та зсунута (1)

від стану q(t–1) у попередній момент часу та вхідного сигналу

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

Функція виходів звичайна та зсунута (2)

автоматів. Автоматами першого роду називаються такі, що описуються рівняннями

q(t) =

(q(t–1), x(t)), (3)
y(t) = (q(t–1), x(t)) (4)

і визначають закон функціонування цих автоматів. Автоматами другого роду називаються такі, закон функціонування яких задається рівняннями

q(t) = (q(t–1), x(t)), (5)
y(t) = (q(t), x(t)), (6)

де t = 0, 1, 2, ... .

Два роди автоматів

вихідний сигнал y(t) не залежить явно від вхідного сигналу x(t),

а визначається тільки станом q(t–1) або q(t). Закони функціонування правильних автоматів визначаються рівняннями

q(t) = (q(t–1), x(t)), (7)
y(t) = (q(t–1)), (8)

q(t) = (q(t–1), x(t)), (9)
y(t) = (q(t)). (10)

Надалі автомати першого роду (рівняння 3–4) називатимемо автоматами Мілі, а правильні автомати другого роду (рівняння 9–10) – автоматами Мура.

Правильні автомати

автоматів

існування сукупності об'єктів:
скінченна множина X = {xi}, iI = {1,

2, ..., m} – вхідний алфавіт автомата;
скінченна множина Y = {yj}, jJ = {1, 2, ..., n} – вихідний алфавіт автомата;
довільний алфавіт Q – алфавіт станів;
довільний елемент q1Q – початковий стан автомата;
відображення :QXQ, що будь-якому qQ і кожній вхідній літері xX зіставляє стан qkQ, тобто функції переходів (q, x);
відображення :QXY, що будь-якому qQ і кожній вхідній літері xX зіставляє вихідну літеру yY, яка визначає звичайну або зсунуту функцію виходів (q,x).

, >, що включає три алфавіти та два відображення, визначає

довільний абстрактний автомат. Якщо A – автомат першого роду, то (q, x) – звичайна функція виходів; якщо A – автомат другого роду, то (q, x) – зсунута функція виходів.
У випадку, коли алфавіт Q скінченний, автомат називається скінченним, у протилежному випадку – нескінченним.
Як визначити відображення, що індукує заданий скінченний автомат A?

Аналітичний метод задання (2)

вхідний сигнал x(t) – довільна літера вхідного алфавіту X, на

виході виникає певний вихідний сигнал y(t) (t = 0, 1, 2, ...) – літера вихідного алфавіту Y. Нехай (X) і (Y) – множини вхідних і вихідних слів автомата A та p = хі1, хі2,…, хік – довільне вхідне слово, тобто p(X). Коли на вхід автомата A, що встановлений у початковий стан, надходить скінченна послідовність x(1) =хі1, ..., x(k) = хік, на виході автомата вона викликає появу однозначної послідовності y(1) = уj1, ..., y(k) = уjk, що визначається відомими відображеннями  і .

Відображення, що індукує автомат (1)

уj2,…, уjk із множини (Y). Тому r = f(p). Для

кожного вхідного слова p(X) зіставляємо відповідне йому вихідне слово r(Y) й у такий спосіб одержуємо шукане відображення f, що індукує скінченний автомат A.

Відображення, що індукує автомат (1)

функції (q, x) і (q, x), що задають закон функціонування

автомата A. Їх можна записати у вигляді матриць, рядки яких відповідають різним літерам вхідного алфавіту X, а стовпчики – різним станам автомата A (літерам алфавіту Q). На перетині xі-го рядка та qk-го стовпчика таблиці переходів (q, x) записується стан ql автомата, до якого він переходить зі стану qk при надходженні вхідного сигналу xi, а у таблиці виходів (q, x) – вихідна літера yj, що з'являється на виході автомата.

Функції (q, x) і (q, x)

вхідним X і вихідним Y алфавітами називаються еквівалентними, якщо індукують

одне й те саме відображення f множини (X) у (Y).
Встановимо взаємозв'язок між автоматами першого та другого роду. Нехай задано автомат другого роду A = . Запишемо функцію переходів (q, x) і зсунуту функцію виходів (q, x) автомата A. Остання виражає залежність y(t) = (q(t), x(t)).

Еквівалентність автоматів

x(t)),
то одержимо рівняння
y(t) = ((q(t–1), x(t)), x(t)) = (q(t–1), x(t)),
що

визначає звичайну функцію виходів '(q, x), яка характеризує автомат першого роду. Таким чином, за рахунок підстановки до зсунутої функції виходів (q, x) автомата другого роду функції переходів (q, x) одержуємо автомат першого роду A' = , який індукує те саме відображення, що й автомат A. Таке зведення автомата другого роду до еквівалентного автомата першого роду називається інтерпретацією автомата другого роду автоматом першого роду. Будь-який автомат першого або другого роду можна інтерпретувати автоматом Мілі.

Інтерпретація автомата

зображення орієнтованого графа, вершинами якого є стани автомата (позначаються qQ),

а біля кожного ребра (qk, ql) записуються літера вхідного алфавіту xiX (викликає перехід автомата зі стану qk до стану ql), і літера вихідного алфавіту yjY (з'являється на виході автомата). Якщо розглядається автомат першого роду, то вихідна літера yj визначається парою (qk, xi), якщо – другого роду, то вихідна літера yj залежить від (ql, xi). Початковий стан автомата позначається q1Q. Орієнтований граф з ребрами, навантаженими літерами вхідного та вихідного алфавітів, однозначно задає певний скінченний автомат.

– геометрична інтерпретація абстрактного автомата. Від графоїда легко перейти до

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

Автомат як орієнтований графоїд

є вершиною першого рангу (коренем) прадерева. Із кореня проводимо m

дуг (m – потужність множини X, m=|X|), які називаються дугами першого рангу. Кожна дуга заходить у вершину другого рангу (m вершин). Із кожної вершини другого рангу проводимо m дуг другого рангу, які закінчуються m2 вершин третього рангу і т.д. Кожній дузі приписується літера xiX і в дужках – літера yjY вихідного алфавіту. Крім того, кожній вершині другого та більших рангів приписується стан qkQ, визначений за графоїдом.

Формування прадерева

графоїда за навантаженим прадеревом – це задача абстрактного синтезу скінченних

автоматів.

Використання прадерев

таблицями переходів і виходів (q, x) та (q, x). Але

частіше використовується квадратна матриця, яку називають матрицею з'єднань автомата. Рядки та стовпчики цієї матриці відповідають різним станам автомата, причому перші рядок і стовпчик відповідають початковому стану q1Q. На перетині qk-го рядка та ql-го стовпчика ставиться літера вхідного алфавіту xiX або диз'юнкція вхідних літер, які викликають перехід автомата зі стану qk до ql, а в дужках – літера вихідного алфавіту yjY або диз'юнкція вихідних літер, що з'являються на виході автомата. Якщо жодна з літер вхідного алфавіту не переводить автомат зі стану qk до ql, то на відповідному перетині ставиться 0.

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

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

Властивість матриці з’єднань