Основи теорії цифрових автоматiв з пам`яттю: Методичні рекомендації та контрольні завдання до виконання лабораторної роботи з дисципліни "Комп’ютерна логіка", страница 3

1.2.2 Абстрактнi автомати першого та другого роду

Абстрактнi автомати бувають першого та другого роду.

Закон функціонування абстрактного автоматупершого роду задається наступними рівняннями:

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

Закон функціонування абстрактного автоматудругого роду задається наступними рівняннями:

Кажуть, що абстрактний автомат другого роду задається зсунутою функцією виходів.

1.2.3 Відображення, що породжуються абстрактними автоматами

Кожен абстрактний автомат породжує деяке відображення

,

яке реалізується в наведений нижче спосiб.

Кожне вхідне слово, тобто слово p=x_i1….x_ik у вхідному алфавіті Х                     (, ) послідовно, лiтера за лiтерою, подається на вхід абстрактного автомату А, що завчасно був встановлений у початковий стан a0.

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

В силу довільності вибору слова , отримуємо деяке відображення ,  таке що .

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

1.2.4 Еквівалентні абстрактнi автомати, теорема про інтерпретацію абстрактного автомату другого роду як абстрактного автомату першого роду

Два абстрактних автомати зі спільними вхідним і вихідним алфавітами називають еквівалентними, якщо вони породжують однакове відображення.

Теорема 1. Для будь-якого абстрактного автомату другого роду  існує еквівалентний абстрактний автомат першого роду , функцiю виходiв якого отримано в результаті підстановки функції переходів абстрактного автомату А до його зсунутої функцiї виходiв.

Дійсно, якщо задано довільний абстрактний автомат А другого роду, то, з закону функціонування абстрактних автоматiв другого роду, отримуємо наступну рiвнiсть: .

Із даної рівності випливає, що абстрактний автомат В першого роду, заданий тією ж функцiєю переходiв d(а,х), що й автомат А, та функцiєю виходiв  (за умови збереження множини станів, початкового стану, вхідного та вихідного алфавітів абстрактного автомату А), породжує те саме відображення множини вхідних слів у множину вихідних слів, що й абстрактний автомат А.

Наведений вище спосіб зведення абстрактних автоматiв другого роду до абстрактних автоматiв першого роду називають інтерпретацією абстрактного автомату другого роду як абстрактного автоматупершого роду.

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

1.2.5 Автомати Мiлi та Мура, скінченні та нескінченні абстрактнi автомати

Автоматами Мілі (А Мілі) називають довільні абстрактнi автомати першого роду.

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

Абстрактнi автомати називають скiнченними (або нескінченними) залежно від того, чи є скінченною (або нескінченною) множина їх станів.

Виходячи із міркувань практики, об’єктом подальшого вивчення будуть скінченні автомати Мілі та Мура.

1.3 Способи задавання абстрактних автоматiв Мілі та Мура

1.3.1 Табличний спосіб задавання абстрактних автоматiв Мілі та Мура

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

Функції переходiв і виходiв задаються таблицями переходів (ТП) і таблицями виходів (ТВ) або за допомогою графів переходів і виходів.

Задавання абстрактних автоматiв за допомогою таблиць переходiв i виходiвпередбачає наступне:

- рядки таблиць позначаються вхідними сигналами абстрактного автомату, а стовпчики – його станами;