Алгоритмов (ГСА) цифровых автоматов.

Начальные языки описания цифровых автоматов. Язык регулярных

Выражений алгебры событий

НАЧАЛЬНЫЕ ЯЗЫКИ ОПИСАНИЯ ЦИФРОВЫХ АВТОМАТОВ

В зависимости от способов задания функций переходов и выходов (d и l) в настоящее время выделяют два класса языков – начальные языки и автоматные языки. В начальных языках автомат описывается на поведенческом уровне, т.е. функции переходов и выходов обычно в явном виде не заданы. Поведение автомата описывается в терминах входных и выходных последовательностей, реализуемых операторов (отображений) или управляющих последовательностей сигналов, воздействующих на операционный автомат.

В автоматных языках поведение автомата задается путем явного задания функций переходов и выходов. Среди начальных языков следует выделить язык регулярных выражений алгебры событий, язык абстрактных схем алгоритмов и язык граф-схем аргоитмов. Но вначале пополним наши знания о видах, свойствах и характеристиках цифровых автоматов.

Начальные языки описания цифровых автоматов. Граф - схемы

алгоритмов (ГСА) цифровых автоматов.

4.2.1. Определение ГСА

ГСА - это ориентированный связный граф, содержащий вершины четырех типов:

Начальная вершина входов не имеет, начальная и операторная вершина имеют по одному выходу, условная вершина имеет два выхода (1, 0), конечная вершина выходов не имеет.

Граф должен удовлетворять следующим условиям:
1) Содержит конечное число вершин, каждая из которых принадлежит одному из перечисленных выше типов;
2) Имеет одну начальную и одну конечную вершину;
3) Входы и выходы вершин, соединяются друг с другом с помощью дуг, направленных от выхода ко входу;
4) Каждый выход соединен, только с одним входом;
5) Любой вход соединяется с одним выходом;
6) Для любой вершины графа существует, по крайне мере, один путь из этой вершины в конечную вершину;
7) Один из выходов условной вершины может соединятся с её входом, что недопустимо для операторной вершины;
8) Каждой условной вершине записывается один из элементов множества;
x = (x_l) l = {1, L}, называют его множеством логических условий, разрешается в различных, условных вершинах, записаны одинаковые элементы множества х;
9) В каждой операторной вершине записывается оператор или микрокоманда y_t подмножество множества y = (y_n) n = {1, N}, называют его подмножеством микроопераций. y_t = (y_t1, …, y_tu, …, y_tU), u = {1, U};

При U = 0 y_t = 0;

Разрешается запись в различных операторных вершинах одинаковых подмножеств множества микроопераций.