Полная версия

Главная arrow Математика, химия, физика arrow Дискретная математика. Сборник задач

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

ЭЛЕМЕНТЫ ТЕОРИИ АВТОМАТОВ

Синтез конечных автоматов

Теоретические сведения

Конечным автоматом называется объект, имеющий конечное число входов, конечное число внутренних состояний, работа которого носит детерминированный (от англ. — «определенный») характер. Если конечный автомат снабдить внешней памятью и допустить ее неограниченное расширение, то такая система будет принадлежать к автоматам третьего типа, например машина Тьюринга. Он показал, что с помощью автоматов третьего типа может быть смоделирована любая система, т.е. реализован любой алгоритм по переработке информации.

Таким образом, можно определить конечный автомат как устройство А=(Р, 5, А, ф, ц/, А0), определенное конечным множеством состояний входов — Р = {р[, р2, ..., руу}, конечным множеством состояний выходов — А = {?ц, Х2, Х5}, конечным множеством внутренних состояний — А = {$!, $2> а также функцией переходов,

определяющей порядок смен внутренних СОСТОЯНИЙ (ф), и функцией выходов, задающей выходные состояния в зависимости от Р и А(ф). Основными являются две модели: Мили и Мура.

Автомат Мили описывается следующими формулами:

  • 1) внутреннее состояние автомата в следующий момент времени зависит от внутреннего состояния автомата в настоящий момент времени и входного сигнала в настоящий момент времени:
    • *(/ + 0 = ф(*(0, р(0);
  • 2) выходной сигнал автомата в настоящий момент времени зависит от входного сигнала в настоящий момент времени и внутреннего состояния автомата в настоящий момент времени:
  • 40 = |/(х(0, р(0)-

Понятие состояния автомата в момент времени t определяется внутренним состоянием автомата и состоянием входа автомата в тот же момент времени:

M(t) = (x(t), р(t)).

Для автомата Мура функции переходов и выходов выглядят следующим образом:

x(t + ) = ф(х(/), р(0);

X(t + 1) = (x(t + 1)) = |/(<р(х(0, р(0) = V'(*(0, р(0)-

Функция выходов для автомата Мура определяется внутренним состоянием автомата (рис. 6.1).

а) б)

Рис. 6.1. Автоматы Мили (а) и Мура (б)

Если рассматривать автомат с учетом его внутренних состояний, то необходимо определить функции перехода (из внутреннего состояния х, во внутреннее состояние ху, не исключая / = у). Задание функций выходов означает, что каждой паре (р,-, х( ) поставлено в соответствие состояние выхода А.,-. Языки, позволяющие таким образом описать автомат, называются стандартными языками. К стандартным языкам относятся: таблицы переходов, таблицы выходов, матрицы переходов, таблицы включений, графы переходов.

Каждая строка (столбец) таблицы переходов соответствует состоянию входов, а каждый столбец (строка) — внутреннему состоянию (табл. 6.1).

Каждая клетка соответствует внутреннему состоянию автомата, в которое он должен перейти в следующий момент времени. Если

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

*2

*3

ХА

Рі

*2

*1

*2

Р2

*3

*3

*4

Рз

*4

*2

Х

Х

в автомате какое-либо состояние не определено, то в соответствующей клетке ставится прочерк. Прочерк означает, что либо это состояние запрещено, либо дальнейшее поведение не определено.

Функция выхода автомата также может быть задана в виде таблицы. При этом вид таблицы зависит от модели автомата (Мили, Мура).

Для автомата Мили столбцы соответствуют внутренним состояниям, строки — входным сигналам, в ячейках — выходные сигналы (табл. 6.2).

Таблица 6.2

Таблица выходов автомата Мили

Хх

*2

*3

р|

К

Р2

а,2

Рз

*1

х2

*1

Запись означает, что если подать на вход автомата, находящегося в состоянии Хх, сигнал р1? то на выходе будет А,,. Для автомата Мура таблица выходов не строится, так как выходной сигнал не зависит от входного. Для автомата Мура строится совмещенная таблица переходов и выходов (табл. 6.3).

Таблица 6.3

Таблица выходов и переходов автомата Мура

а2

*1

Хх

*2

*3

р|

Хх

*2

*3

р?

Хх

X")

Рз

*3

Как и для синхронного автомата, каждая ячейка таблицы переходов асинхронного автомата соответствует внутреннему состоянию,

в которое перейдет автомат. Это состояние определяется внутренним состоянием в предыдущий момент времени и поданным на вход сигналом. Устойчивое состояние асинхронного автомата, т.е. состояние, соответствующее устойчивому такту, обозначается в таблице переходов круглыми скобками. Неустойчивое состояние записывается без скобок (табл. 6.4).

Таблица 6.4

Таблица переходов для асинхронного автомата

Рі

Р2

Рз

*1

*2

*2

*3

*2

*3

да

да

*3

*6

(У,)

*4

*3

*5

да

*4

*6

да

*6

Входной сигнал можно менять, когда автомат перешел в новое устойчивое состояние. Если устойчивого состояния нет, то происходит зацикливание (неустойчивое состояние). Если автомат переходит из одного устойчивого внутреннего состояния под воздействием входного сигнала в другое состояние, то входной сигнал можно изменять только при «попадании» автомата в устойчивое состояние. Переход автомата из одного устойчивого состояния в другое устойчивое состояние может осуществляться через несколько неустойчивых состояний.

Особенность асинхронных автоматов состоит в том, что записывается последний выходной сигнал (при устойчивом состоянии). В столбце внутренних состояний записываются только устойчивые состояния. Выходные сигналы соответствуют устойчивому состоянию (табл. 6.5).

Таблица 6.5

Таблица выходов для асинхронного автомата

Рі

Р2

*1

*1

*2

*2

*3

^2

^3

*4

А.,

Граф автомата — это связный граф, вершины которого соответствуют внутренним состояниям автомата, а дуги определяют переходы между состояниями.

Для автомата Мили две вершины графа автомата х,- и х- соединяются дугой, направленной отх, кху , если в автомате имеется переход из состояния х, в состояние Х-. Дуге графа приписывается входной сигнал р и выходной сигнал X. Если переход автомата из состояния х,-в состояние ху происходит под воздействием нескольких входных сигналов, то дуге приписываются все эти сигналы через знак V (дизъюнкции). Граф переходов автомата Мили представлен на рис. 6.2.

Граф переходов для автомата Мили

Рис. 6.2. Граф переходов для автомата Мили

Для автомата Мура выходной сигнал зависит только от внутреннего состояния автомата, поэтому он приписывается вершинам графа, соответствующим определенному внутреннему состоянию автомата. Граф переходов автомата Мура представлен на рис. 6.3.

Граф переходов для автомата Мура

Рис. 6.3. Граф переходов для автомата Мура

Особенностью графа асинхронного автомата является следующее: для того чтобы автомат поддерживал себя в устойчивом состоянии, до тех пор пока не придет новый входной сигнал, необходимо указать дугу, зацикливающую вершину саму на себя с тем же входным сигналом. Граф переходов асинхронного автомата представлен на рис. 6.4.

Граф переходов для асинхронного автомата

Рис. 6.4. Граф переходов для асинхронного автомата

Задачи

Задача 6.1. Выяснить, является ли следующий граф графом переходов некоторого автомата (рис. 6.5).

а, а

Условия задачи 6.1

Рис. 6.5. Условия задачи 6.1

Задача 6.2. Построить таблицу автомата, заданного следующим графом переходов (рис. 6.6).

Задача 6.3. Построить граф переходов автомата, заданного таблицей (рис. 6.7).

О 1 2

Условия задачи 6.3

Рис. 6.7. Условия задачи 6.3

Я

Ь Ь

Задача 6.4. Автомат, у которого (7 = {0, 1, 2}, А = В = {0, 1}, задан каноническими уравнениями

ф(4, а) = д + а (гпобЗ),

4/(4, а) =

если 4 < 2, если 4 = 2.

V

Построить граф переходов этого автомата.

Задача 6.5. Автомат Кзадан каноническими уравнениями

Гб(Г) = <7(/) + я(0 (тобЗ), | д{1 + 1) = а(і) + 1 (тобЗ),

где А = В = 0 = {0, 1, 2}. Построить граф переходов автомата V.

Задача 6.6. Автомат Ктаков, что:

А = {0, 1} х {0, 1};

В = 0 = {0, 1};

ср(4, (х, у)) = 4 + ху (той 2);

|/(<7, (х, у)) = <7 + х + у (той 2).

Построить таблицу переходов автомата V.

Задача 6.7. Написать канонические уравнения автомата, заданного следующим графом переходов (рис. 6.8).

Задача 6.8. Для автомата, заданного таблицей, построить граф переходов. Задать этот автомат системой булевых функций (табл. 6.6).

ь, ь

Таблица 6.6

Условия задачи 6.8

Я

X

0

1

2

3

0

1; 1

3; 0

2; 0

2; 0

1

2; 1

2; 0

3; 0

3; 0

Задача 6.9. Для автомата, заданного таблицей, построить граф переходов. Задать этот автомат системой булевых функций (табл. 6.7).

Таблица 6.7

Условия задачи 6.9

Я

X

0

1

2

3

0

0; 1

1; 1

2; 1

3; 1

1

0; 0

0; 1

3; 1

2; 1

Задача 6.10. Для автомата, заданного таблицей, построить граф переходов. Задать этот автомат системой булевых функций (табл. 6.8).

Таблица 6.8

Условия задачи 6.10

Я

X

0

1

0

0; 0

0; 1

1

0; 1

1; о

2

0; 1

1; о

3

1; о

1; 1

Задача 6.11. Для автомата, заданного таблицей, построить граф переходов. Задать этот автомат системой булевых функций (табл. 6.9).

Таблица 6.9

Условия задачи 6.11

Я

X

0

1

2

3

0

1; о

2; 0

2; 1

3; 0

1

3; 0

3; 1

2; 1

1; о

Задача 6.12. Для автомата, заданного таблицей, построить граф переходов. Задать этот автомат системой булевых функций (табл. 6.10).

Таблица 6.10

Условия задачи 6.12

Я

X

1

2

3

0

2; 0

2; 1

3; 1

1

1; 1

3; 0

3; 1

2

1; 1

2; 1

1; о

Задача 6.13. Для автомата, заданного таблицей, построить граф переходов. Задать этот автомат системой булевых функций (табл. 6.11).

Таблица 6.11

Условия задачи 6.13

Я

X

0

1

0

0; 0

1; 1

1

1; 1

1; 1

2

1; 1

1; 1

3

0; 0

1; 1

Задача 6.14. Для автомата, заданного таблицей, построить граф переходов. Задать этот автомат системой булевых функций (табл. 6.12).

Таблица 6.12

Условия задачи 6.14

Я

X

1

2

3

0

1;0

2; 1

3; 2

1

2; 1

2; 1

3; 2

2

3; 2

2; 1

3; 2

3

1; о

2; 1

3; 2

Задача 6.15. Для автомата, заданного таблицей, построить граф переходов. Задать этот автомат системой булевых функций (табл. 6.13).

Таблица 6.13

Условия задачи 6.15

Я

X

0

1

2

3

0

0; 0

1; 1

3; 1

2; 0

1

2; 0

0; 1

3; 1

1; о

 
<<   СОДЕРЖАНИЕ   >>