Язык граф-схем алгоритмов (язык ГСА)

Язык предложен советским ученым Л. А. Калужиным в 1959 г. ГСА – ориентированный связный граф, содержащий одну начальную вершину, одну конечную вершину, а также произвольное число операторных и условных вершин [1, 2]. В операторных вершинах стрелка всегда входит сверху и выходит снизу, а в условных вершинах – входит сверху, а выходит снизу и с одной из сторон, либо справа и слева (рис. 1.5).

Рис. 1.5. Виды вершин ГСА:
а) начальная; б) конечная; в) операторная; г) условная

ГСА должна удовлетворять следующим требованиям.

1. Выходы вершин соединяются с входами других вершин. Исключение – условная вершина, один из выходов которой может соединяться с собственным входом (возвратная вершина – рис. 1.6).

Рис. 1.6. Возвратная вершина

2. Каждый выход соединяется только с одним входом.

3. Каждый вход соединяется не менее чем с одним выходом.

4. Через любую вершину ГСА должен существовать хотя бы один путь от начальной вершины к конечной.

5. В каждой вершине записывается один из операторов либо одно из условий. Допускается в различных вершинах записывать одинаковые операторы или условия.

Существуют содержательные и символические ГСА. В содержательных ГСА внутри вершин записываются операторы или условие в виде:

<Переменная>: = <Значение> – для операторной вершины;

<Условие> = <Значение>? – для условной вершины.

<Переменная> в операторной вершине – это выходной сигнал автомата.

<Значение> – эквивалент логического значения. Например, открыт/закрыт, включен/выключен.

Содержательная ГСА обычно используется на первом этапе разработки автомата, когда известно только его словесное описание. В этом случае ГСА будет графической формой словесного алгоритма работы автомата.

Далее от содержательной ГСА переходят к символьной. При этом в операторной вершине записывается один из элементов множества операторов, а в условной – одно из условий.

Далее от символической ГСА переходят к описанию автомата на стандартном языке. В зависимости от модели автомата, как правило, получаются различные описания автомата на стандартном языке. При большом числе вершин и связей между ними ГСА теряет наглядность и становится громоздкой. В этом случае используют другую форму записи ГСА – прямую таблицу переходов.