Матричные схемы алгоритмов (МСА) цифровых автоматов.

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

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

1. Каждый выход из любой вершины должен быть соединён только с одним входом в какую-либо вершину.
2. Любая вершина лежит хотя бы на одном пути из Y_н в Y_к.
3. Один из выходов условной вершины может соединяться с её входом, что недопустимо для операторных вершин.

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

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

_· символы операторных вершин 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

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

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 имеют вид:

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