ТЕОРІЯ АБСТРАКТНИХ АВТОМАТІВ

Автомат

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

• Абстрактний автомат (АА) - дискретний перетворювач інформації; множина, що складається з шести елементів:
• S = {X, Q, Y, δ, λ, q1} S - абстрактний автомат;
• X – множина вхідних символів (вхідний алфавіт автомата): X = {x1, ... ,xm};
• Q – множина станів автомата: Q= {q1, ... ,qn};
• Y – множина вихідних символів (вихідний алфавіт автомата): Y= {y1, ... ,yp};
• δ - функція переходів автомата з одного стану в інший: qj= δ(qi,xk), де: qj - наступний (новий) стан автомата; qi - поточний стан автомата; xk - поточний вхідний символ;
• λ – функція виходів: yl= λ(qi,xk);
• q1 – початковий стан автомата (застосовується також позначення q0).
• Автомат називається скінченним, якщо множини X, Q, Y - скінченні

Загальні відомості

Подання абстрактного автомата

На рисунку t - дискретний час: t =nT, де T - інтервал (такт), що розділяє дискретні моменти часу;

якщо T = 1, то t = n, тобто дискретний час зіставляється впорядкованому ряду натуральних чисел.

Загальні відомості

• Абстрактний автомат (АА) можна розглядати як "чорну скриньку" з одним входом і одним виходом, з яким можна експериментувати, не знаючи, що знаходиться всередині.
• Вихідний символ (y Y) залежить не тільки від вхідного символу (x X), а й від того, в якому стані (q Q) перебуває автомат.
• Автомат функціонує у дискретному часі; це означає, що елементи опису автомата задані лише у згадані вище дискретні моменти.
• Припустимо, що з деякого початкового, наприклад, нульового моменту часу на вхід автомата подаються вхідні символи, що утворюють вхідне слово деякої довжини (довжина будь якого i-го слова вимірюється кількістю символів).
• На виході отримуємо вихідне слово тієї ж довжини.

Перетворення вхідних слів у вихідні

Загальні відомості

• Автомат може розглядатися як перетворювач вхідних слів у вихідні із збереженням довжини слів.
• Символи алфавітів, присутні на вході та виході автомата, також називатимемо вхідними та вихідними сигналами.
• На практиці широкого поширення набули дві основні моделі, що описують функціонування АА:
• 1. Модель Мілі;
• 2. Модель Мура

Модель Мілі

• Закони функціонування автомата Мілі представлені так:
• q(t+1) = δ(q(t), x(t)) y(t) = λ(q(t), x(t))
• t - поточний момент часу; t+1 - наступний момент часу;
• q(t+1) - стан автомата в наступний момент часу;
• q(t), x(t), y(t) – елементи опису автомата в даний момент часу

Модель Мура

• Закони функціонування автомата Мура представлені так:
• q(t+1) = δ(q(t),x(t)) y(t) = λ(q(t))
• У моделі Мура вихідний сигнал явно залежить від стану, а побічно – і від вхідного сигналу.
• Будь який автомат можна спроектувати за тією чи іншою моделлю.

Способи задання автоматів

Два основні способи задання автоматів: табличний і графовий.

​

​

Автомат Мілі

​

Для автомата Мілі табличний спосіб полягає у побудові двох таблиць:

​

таблиці переходів (ТП) та таблиці виходів (ТВ).

Табличний спосіб

Табличний спосіб: а - таблиця переходів, б - таблиця виходів

Приклад: а) Таблиця переходів

Приклад: б) Таблиця виходів

Автомат Мура

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

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

приклад. Таблиця переходів та виходів

Графовий спосіб

• Автомат є орієнтованим зв'язним графом (орграфом), вершини якого відповідають станам автомата, а дуги – переходам зі стану на стан.
• Позначення вхідних та вихідних сигналів розподіляються в автоматах Мілі та Мура по різному.

Побудуємо графи для автоматів Мілі та Мура за наведеними вище таблицями

Подання автомата Мілі у вигляді графа

Подання автомата Мура у вигляді графа

• Зауваження:
• В автоматі Мілі вихідний сигнал виробляється при переході, а в автоматі Мура присутній протягом усього періоду дискретного часу, поки автомат перебуває в даному стані.

Детермінований автомат

• - Автомат, в якому є повна визначеність переходів з усіх станів залежно від вхідних сигналів (під дією одного і того ж сигналу автомат не може переходити з будь якого стану в різні стани).
• Фрагмент графа, зображений малюнку 7, неспроможна ставитися до детермінованому автомату

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

Стан автомату qi

називається стійким, якщо для будь-якого вхідного сигналу хк, такого, що δ(qs,xk) = qi, справедливе співвідношення:

δ(qi,xk) =qi. (тут qs - стан, що передує qi).

Це означає, що автомат не змінює свого стану при повторенні на наступному такті сигналу, що привів його в стан qi.

Фрагмент графа, що ілюструє стійкість стану, наведено малюнку.

Стійкий стан автомата

Автомат називається асинхронним,

якщо кожен його стан qi Q (i= 1, ... , n) стійкий,

інакше автомат називається синхронним.

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

Приклади абстрактних автоматів, які виконують корисні дії

• Автомат для затримки сигналу одного такту (для запам'ятовування одного такту)
• Таблиця переходів та таблиця виходів:

• Оскільки автомат є двійковим, введемо позначення: x0 = y0 = 0; x1= y1= 1

​

Граф автомата для затримки сигналу на один такт

Простий аналіз показує,

• що вихідний сигнал у поточному такті повторює вхідний, який був на такт раніше.
• Автомат для перевірки двійкової послідовності на парність

Граф автомата для перевірки двійкової послідовності на парність

Аналіз показує,

• що "0" на виході автоматично виробляється при парному числі одиниць на вході, а "1" на виході виробляється при непарному числі одиниць на вході.
• Обидва розглянуті автомати мають "слабку" пам'ять, але слабку в різному сенсі.
• У першого автомата "коротка" пам'ять у часі (пам'ятає лише один сигнал).
• У другого автомата пам'ять "довга" (довжина вхідної послідовності може бути будь-який), але він розрізняє (розпізнає) лише два класи послідовностей.

Автомат для затримки сигналу на два такти

• Автомат має чотири стани, закодовані двома двійковими розрядами: q0= 00; q1 = 01; q2 = 10; q3 = 11

Граф автомата для затримки сигналу на два такти

Переваги застосованого кодування:

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

Двійковий послідовний суматор, реалізований для одного розряду вхідного коду

​

• Автомат має два стани:
• q0 – немає перенесення (складання цифр операндів не вимагає обліку одиниці перенесення з попереднього розряду коду);
• q1 –є перенесення (одиниця перенесення має бути врахована)

Граф однорозрядного двійкового послідовного суматора

У чисельнику "дроби", записаної за кожної з дуг графа, Вказані цифри доданків; у знаменнику – результат підсумовування у поточному розряді. Суматор дозволяє підсумовувати двійкові послідовності довільної довжини.

Поведінка ізольованого синхронного автомата

• Ізольований автомат - автомат, на вході якого є сигнал, що має постійне значення, що еквівалентно "відключення" входу.
• Якщо ізольований автомат є синхронним, переходи з одного стану до іншого можливі, але при цьому виключені розгалуження шляхів, що відображають послідовності переходів (автомат є детермінованим).
• Отже, автомат з кінцевим числом станів (кінцевий автомат) неминуче повинен потрапити в стан, в якому вже знаходився раніше, і на діаграмах переходів обов'язково буде присутній поглинаючий стан або цикл.

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

Поведінка ізольованого синхронного автомата