Начальные языки

Начальные языки трактуются как языки неявного задания ЦА или языки явного описания автомата на начальных этапах его рассмотрения. К таким языкам относятся: язык регулярных выражений алгебры событий, логическая схема алгоритма (ЛСА), графическая схема алгоритма (ГСА), матричная схема алгоритма (МСА), функциональная микропрограмма (ФМП), система формул перехода (СФП), входной, внутренний и выходной языки (алфавиты), законы функционирования.

СА, ГСА, МСА, ФМП и СФП подробно описаны в [11]. Тем не менее

они здесь в учебных целях кратко рассматриваются.

Рис.9. Классификация языков описания автоматов

2.1.1. Графическая схема алгоритма

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

Поскольку ГСА предложена для алгоритмов операций ЭВМ, то в ней нет средств для отражения ввода-вывода.

Вместо блоков в ГСА используются вершины: начальные Y₀ , конечные Y_к, операторные вершины Y₁,Y₂, … , условные вершины X1,X2, … .

На рис.10 показана СА классического алгоритма нахождения наиболь-

шего общего делителя (ННОД),

где: А и С - исходные числа,

НОД - наибольший общий делитель.

Видно, что заданные числа при А<С меняются местами (блоки 5¸7). По-

скольку после этого получается А >С, то число А заменяется на значение

А - С. Подобные циклы повторяются до получения А= С (блоки 3¸8), число А и будет требуемым результатом (блок 9).

Имеются отличия применительно к условным вершинам. Прежде всего, условие (чаще всего отношение) записывается в закодированном виде.

2

3

=

¹

4 >

10

5 >

11

7

Рис. 10. СА ННОД чисел A и D

Если оно выполняется, то результату присваивается единичное значение, в противном случае - нулевое значение. С учетом этого выходы вершины отмечаются указанными значениями вместо “да” и “нет”.

Содержательная и закодированная граф-схемы алгоритмов представлены на рис.11 и 12 соответственно, коды микроопераций у_i, микрокоманд Y_i и условий XI - в табл.1.

D: =НОД

Y₃

Y₀

1 1

0 0

Y₂

Рис. 11. ГСА ННОД Рис.12. Закодированная ГСА ННОД

Таблица 1

Условия корректности ГСА похожи на условия корректности схемы алгоритма [14]:

1) у ГСА должна быть одна начальная и одна конечная вершины;

2) каждый выход соединен только с одним входом;

3) каждый вход соединен, по крайней мере, с одним выходом;

4) выходы условных вершин помечаются с помощью цифр “0” и “1”;

5) из начальной вершины должен быть путь к любой вершине;

6) из любой вершины должен быть путь в конечную вершину;

7) для любых наборов логических условий должен быть путь из началь-

ной вершины в конечную вершину.

2.1.2. Матричная схема алгоритма

Матричная схема алгоритма (МСА) представляет собой квадратную матрицу, строки которой соответствуют вершинам с выходами, столбцы - вершинам с входами. На пересечениях строк и столбцов записываются функции перехода. Такая функция представляет собой конъюнкцию кодов логических условий (логических переменных), переменная пишется без инверсии, если выход осуществляется по 1, в противном случае переменная пишется c инверсией. Функция перехода, равная 1, соответствует безусловному переходу.

Для указанного выше алгоритма МСА (МСА ННОД) представлена в табл.2

Таблица 2

Для МСА можно сформировать условия корректности:

1) в МСА не должно быть строки Y_k;

2) в МСА не должно быть столбца Y₀;

3) должны быть столбец Y_k и строка Y₀;

4) не должно быть пустых строк и столбцов;

5) на строке не должно быть одинаковых функций перехода;

6) на строке не должно быть сочетаний 1 и функций перехода через логические переменные;

7) в столбце могут быть одинаковые функции перехода;

8) на строке может быть только одна 1;

9) дизъюнкция всех функций переходов на строке должна быть равна единице;

10) разные строки с одинаковыми функциями переходов разрешается оформ-

лять в одной строке с указанием всех индексов вершин старта.

По МСА можно упрощать алгоритмы и, следовательно, автоматы.

2.1.3. Функциональная микропрограмма

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

Применительно к Ф - языку [9] ФМП имеет следующую структуру:

1) заголовок с ключевым словом “АЛГОРИТМ”;

2) совокупность описаний с ключевыми словами “ВХОДНЫЕ”, ”ВНУТРЕННИЕ”, ”ВЫХОДНЫЕ”;

3) НАЧАЛО;

4) тело;

5) окончание с ключевым словом “КОНЕЦ”.

ФМП алгоритма ННОД можно представить в следующем виде:

АЛГОРИТМ ННОД;

ВХОДНЫЕ А(1:32),С(1:32);

ВНУТРЕННИЕ: А(1:32),С(1:32),НОД(1:32);

ВЫХОДНЫЕ: НОД(1:32);

НАЧАЛО

М3: ПЕРЕЙТИ ЕСЛИ Х1 ТО М1;

ПЕРЕЙТИ ЕСЛИ Х2 ТО М2;

Y1;

Y2;

Y3;

М2: Y4;

ПЕРЕЙТИ М3;

М1: Y5;

КОНЕЦ.

По ФМП, как и по предыдущим способам описания, можно организовать алгоритмический процесс. Пусть А=8, С=6, тогда данный процесс следует отразить следующим образом:

начало;

1 цикл: 8=6, Х1=0, 8>6, X2=1, ®М2, Y₄, А=2, В=6, ®М3;

2 цикл: 2=6, Х1=0, 2>6, Х2=0, Y₁, НОД=2, А=6, В=2, А=4, ®М3;

3 цикл: 4=2, Х1=0, 4>2, X2=1, ®M2, Y₄, A=2, B=2, ®M3;

4 цикл: 2=2, Х1=1, ®М1;

НОД=2;

конец.

Для исходных чисел 8 и 6 действительно наибольший общий делитель равен 2.

Для ФМП существуют и условия корректности:

1) должен быть заголовок;

2) данной меткой может быть помечен только один оператор (одна строка);

3) в операторах перехода могут использоваться одинаковые метки;

4) строка после оператора безусловного перехода должна иметь метку;

5) на строке может быть записана только одна микрокоманда или один оператор перехода.

2.1.4. Система формул переходов

Все переходы, соответствующие строке МСА, можно отразить в формуле переходов. Формул будет столько, сколько имеется строк в МСА. Получается система формул перехода (СФП).

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

Между левой и правой частями формулы ставиться стрелка ® , которая отражает переходы от вершины левой части к одной из вершин правой части.

Переход совершается к той вершине, соответствующая функция перехода которой становится равной единице.

Для рассматриваемого алгоритма СФП включает в себя:

__ __ __

Y_0,4 ® Х1Х2Y₁+Х1Х2Y₄+Х1Y₅;

Y₁ ® Y₂;

Y₂ ® Y₃;

Y₃ ® Y₄;

Y₅ ® Y_K.

Применительно к СФП можно сформулировать условия корректности:

1) не должно быть формулы перехода для Y_к;

2) в правой части любой формулы не должно быть вершины Y₀;

3) логическая сумма всех функций перехода любой формулы должна быть равна единице;

4) конъюнкция любой пары функций перехода формулы должна быть равна нулю;

5) в формуле не может быть одинаковых функций перехода;

6) у данной операторной вершины формул переходов может быть одинаковая функция перехода.

СФП позволяет производить формальные преобразования, упрощать алгоритм, следовательно, и автомат.