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

- початковий стан позначають у першому ліворуч стовпчику;

- на перетині х-го рядка та а-го стовпчика в таблицi переходiв проставляють значення d(а,х), а в таблицi виходiв (звичайній або зсунутій) – значення l(а,х).

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

Для автомату Мура, зсунута функцiя виходiв зводиться до одного рядка.

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

У позначенiй таблицi переходiв, над кожним станом а_і, що позначає певний стовпчик таблицi переходiв, ставиться відповідний даному стану вихідний сигнал λ(а_і).

Кажуть, що в довільному абстрактному автоматi Мура кожен стан аі позначений відповідним йому вихідним сигналом λ(а_i).

1.3.2 Графовий спосіб задавання абстрактних автоматiв Мілі та Мура

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

Граф абстрактного автомату А є комбінацією наступних об`єктiв:

- вершин графу, що ототожнюються зі станами абстрактного автомату(зображуються на рисунках за допомогою кiл);

- ребер графу, щоототожнюються з вхідними сигналами абстрактного автомату (зображуються на рисунках за допомогою стрілок, що з’єднують вершини).

Якщо вхідний сигнал х викликає перехід абстрактного автомату зі стану а_і до стан а_к, то на графі даному переходу відповідає рисунок наступного виду:

 

Рисунок 1

Також не включається випадок, коли вершини аіта ак співпадають:

 

Рисунок 2

Побудований у вказаний вище спосiб граф абстрактного автомату А задає лише функцiю переходiвданого автомату.

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

Якщо позначена вхідним сигналом х стрілка з’єднує вершини а_і та а_к, то їй приписується наступний вихідний сигнал:

- у випадку абстрактного автомату першого роду - λ1(а_і,х), де λ1 є звичайною функцiєю виходiв абстрактного автомату;

- у випадку абстрактного автомату другого роду - λ2(а_к,х), де λ2 є зсунутою функцiєю виходiв абстрактного автомату.

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

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

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

Нехай автомат Мура задано позначеною таблицею переходів 1.

Таблиця 1

	U	U	V	V
	1	2	3	4
X	2	3	3	2
Y	1	4	4	1

Даній таблицi переходiв відповідає граф, представлений на рисунку 3.

Рисунок 3

1.3.3 Інтерпретація абстрактного автомату Мура, заданого таблично або графово, як абстрактного автомату Мілі

При обох способах задавання абстрактного автомату, особливо просто здійснюється інтерпретація довільного автомату Мура А, як автомату Мiлi В:

- у випадку задавання А позначеною таблицею переходiв, для отримання еквівалентного автомату В, необхідно у позначенiй таблицi переходiв автомату Мура замість станів підставити вихідні сигнали, що позначають їх;

- у випадку задавання А графом, для отримання з А  В, досить позначити вихідними сигналами не вершини, а стрілки, що входять у відповідні вершини.