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

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

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

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

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

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

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

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; Разрешается запись в различных операторных вершинах одинаковых подмножеств множества микроопераций.

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

алгоритмов цифровых автоматов.

Логические схемы алгоритмов

В ряде случаев вместо ГСА используются логические схемы алгоритмов , представляющие алгоритм функционирования цифрового автомата в виде конечной строки. Эта строка содержит символы операторов, символы логических условий, а также верхние и нижние стрелки, которым приписаны натуральные числа (например, должны удовлетворять следующим условиям:

в строке может быть записан только один начальный оператор один конечный оператор

перед оператором и после оператора стрелок не должно быть;

вслед за каждым логическим условием всегда стоит верхняя стрелка;

не должно существовать двух нижних стрелок с одинаковыми цифрами;

для каждой верхней стрелки должна быть одна нижняя стрелка.

Рис. 12.33 (см. скан)

Рис. 12.84

для каждой нижней стрелки должна быть хотя бы одна верхняя стрелка

В ЛСА, как и в ГСА, операторы обозначают буквами с индексом, а логические условия — буквами х с индексом.

Рассмотрим ЛСА конкретного цифрового автомата: Эта ЛСА имеет начальный оператор конечный оператор четыре оператора три логических условия Эквивалентная ГСА представлена рис. 12.34. Алгоритмперехода от ЛСА к ГСА очевиден. Соответствующая ГСА имеет начальную и одну конечную вершины, а число ее операторных вершин равно числу операторов в Выход начальной вершины ГСА соединяется дугой со входом вершины, соответствующей в ЛСА ближайшему справа от оператору или логическому условию. Аналогичным образом в ГСА проводятся дуги из операторных вершин. Единичный выход условной вершины соединяется со входом вершины, расположенной в ЛСА справа от Если после логического условия в ЛСА стоит верхняя стрелка то нулевой выход условной вершины соединяется со входом вершины, соответствующей в ЛСА оператору или логическому условию, перед которым стоит стрелка Для реализации безусловного перехода достаточно вместо условия использовать константу читаются слева направо и используются в тех случаях, когда нужна компактная вапись алгоритма (например, при машинной обработке). Следует отметить, что возможен переход от ГСА к ЛСА, однако он более сложен и используется редко.