ГСА это ориентированный связный граф, содержащий одну начальную вершину, произвольное число условных и операторных вершин и одну конечную вершину (рисунок 2.1). Условная вершина имеет два выхода, которые отмечаются символами 1 (выполнение условия) и 0 (невыполнение условия).
ГСА удовлетворяет следующим условиям:
1. входы и выходы вершин соединяются дугами, всегда направленными от выхода к входу.
2. каждый выход соединен только с одним входом.
3. любой вход соединен по крайней мере с одним выходом.
4. любая вершина графа лежит по крайней мере на одном пути из начальной в конечную вершину.
5. в каждой условной вершине записывается только один из элементов множества логических условий. Разрешается в разных условных вершинах записывать одинаковые элементы из множества логических условий.
6. в каждой из операторных вершин записывается один из элементов множества операторов. Разрешается в различных операторных вершинах запись одинаковых элементов из множества операторов.
Рисунок 2.1 - Условные графические обозначения вершин ГСА: a) начальная, б) конечная, в) промежуточная, г) условная вершины
Для автомата Мили разметка ГСА определяется следующим образом.
1. Символом начального состояния a1 отмечается вход вершины, следующей за начальной, а так же вход конечной вершины ГСА.
2. Выходы всех вершин, следующих за операторными, отмечаются различными символами a2…ai …an.
3. Выходы всех вершин ГСА, следующих за операторными должны быть отмечены только одним единственным индивидуальным символом ai.
С учетом этих правил ГСА будет размечена, как показано на рисунке 2.2.
Рисунок 2.2 - Размеченная ГСА синхронного УА
Условиями курсового проекта синхронный УА задан в виде не инициального, то есть не имеющего строго определенного начального состояния, из которого УА начинает свою работу. Таким внутренним состоянием, изображенным на рисунке 2.2, может, например, быть состояние a1.