2. Граф-схемы алгоритмов (гса) функционирования автоматов.

ГСА – это ориентированный связанный граф, содержащий одну начальную Y_н, одну конечную Y_к, множества условных X={x₁ x₂ ..x_n} и операторных Y={y₁ y₂ ..y_m} вершин.

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

6. Каждый выход из любой вершины должен быть соединён только с одним входом в какую-либо вершину.

7. Любая вершина лежит хотя бы на одном пути из Y_н в Y_к.

8. Один из выходов условной вершины может соединяться с её входом, что недопустимо для операторных вершин.

В операторных вершинах могут помещаться выходные буквы автомата, в условных – входные (иначе – логические условия). В условных вершинах проверяется наличие на входе автомата соответствующей буквы. В зависимости от того, та ли буква на входе или нет (выходы «1» или «0» условной вершины) будет соответствующий переход по ГСА. Если при этом встречается операторная вершина, то автомат выдаёт соответствующую выходную букву.

На рис.1 приведен пример ГСА. В нашем примере символы x_i и y_i – это просто условное обозначение соответствующих условных и операторных вершин (но не входные и выходные буквы автомата!). Обычно начальную и конечную вершины ГСА обозначают несколько отлично от остальных операторных вершин (смотри рис.1: вершины Y_н и Y_к,).

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

ЛСА – это более компактная, но менее наглядная форма представления ГСА. В ЛСА используют:

• символы операторных вершин Y_j

• символы условных вершин X_j

• ^I, ^I –верхние и нижние стрелки. Верхние стрелки ^I ставятся после символов условных вершин X_j и их надстрочный индекс I указывает номер нижней стрелки ^I , к которой надо перейти, если X_j = 0)

• W ^I – безусловный переход, где i - номера переходов к нижней стрелке ^I.

Для правильной записи ЛСА отметим на ГСА (рис.1) номерами 1, 2 и 3 вершины, к которым подходят более одной стрелки. Перед символами этих вершин в ЛСА ставятся нижние стрелки с отмеченными на ГСА номерами.

Если возникают затруднения при записи ЛСА, можно вводить дополнительные нижние и верхние стрелки и использовать безусловный переход W ^I.

ЛСА, соответствующая ГСА на рис.1 имеет вид:

Y_н ¹ X₁ ¹ Y₁² Y₂ X₂² Y₄ X₃³ Y₃ ³ Y_k

4. Формулы переходов.

Формулы переходов описывают все пути между операторными вершинами в ГСА . Они имеют вид:

Y_m  U b_msּY_s – и описывают все возможные переходы из вершины Y_m в вершины Y_s, где:

b_ms = ∩ X_sj – произведение логических условий, записанных в условных

^j вершинах ГСА, лежащих на пути из Y_m в Y_s . Если выход из условной вершины X_k по стрелке «1», то в ∩ записывается X_k, если «0» – то записывается X_k ( - символ операции «инверсия»).

Формулы переходов, соответствующие ГСА на рис.1 имеют вид:

Y_н  X₁Y₁  X₁Y_н

Y₁  Y₂

Y₂  X₂Y₂  X₂Y₄

Y₃  Y_к

Y₄  X₃Y₃  X₃Y_к

5. Матричные схемы алгоритмов (мса).

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

Ym\ Ys	Yн	Y1	Y2	Y3	Y4	Yк
Yн	X1	X1
Y1			1
Y2			X2		X2
Y3						1
Y4				X3		X3