Тема 1.2. Начальные языки описания цифровых автоматов. Язык регулярных
выражений алгебры событий.
Язык регулярных выражений алгебры событий использует следующие понятия:
Входной алфавит: Z={z1, z2, ... zn}
Выходной алфавит: W={w1, w2, … wm}
Множество событий: S={s1, s2, … sk}
Регулярные выражений, описывающие работу автомата записываются из букв входного алфавита с применением следующих операций:
Zi Zj – объединение (дизъюнкция),
Zi Zj или Zi Zj – конъюнкция,
{Zi}
– итерация.
Всякое
регулярное выражение определяет
некоторое событие siS.
Если это событие наступило, то выдаётся
соответствующая буква w
W.
Например.
Записать регулярное выражение для автомата, работающего с входным алфавитом Z={z1, z2, z3, z4, z5} и имеющего выходной алфавит W={ w1, w2}. Поведение автомата следующее:
Если последовательность входных букв (входное слово) начинается с z1, а заканчивается цепочкой z2 z3, то автомат должен выдать выходную букву w1 (событие s1).
Если слово начинается с буквы z2, а заканчивается z4 или z5, то автомат должен выдать букву w2 (событие s2).
s1/w1=z1{z1 z2 z3 z4 z5}z2 z3,
s2/w2=z2{z1
z2
z3
z4
z5}(z4
z5).
Подобное описание появилось как результат развития теории формальных грамматик и распространения этой теории на автоматы. Оно представляет интерес для теоретических исследований, а при проектировании технических устройств используется редко.
Лекция 2.
Тема 1.3. Граф - схемы алгоритмов (гса) цифровых автоматов.
Логические схемы алгоритмов цифровых автоматов.
Матричные схемы алгоритмов (МСА) цифровых автоматов.
Г
СА
– это ориентированный связанный граф,
содержащий одну начальную Yн,
одну конечную Yк,
множества условных X={x1
x2
..xn}
и операторных Y={y1
y2
..ym}
вершин.
ГСА должна удовлетворять следующим условиям:
Каждый выход из любой вершины должен быть соединён только с одним входом в какую-либо вершину.
Любая вершина лежит хотя бы на одном пути из Yн в Yк.
Один из выходов условной вершины может соединяться с её входом, что недопустимо для операторных вершин.
В операторных вершинах могут помещаться выходные буквы автомата, в условных – входные (иначе – логические условия). В условных вершинах проверяется наличие на входе автомата соответствующей буквы. В зависимости от того, та ли буква на входе или нет (выходы «1» или «0» условной вершины) будет соответствующий переход по ГСА. Если при этом встречается операторная вершина, то автомат выдаёт соответствующую выходную букву.
Логические схемы алгоритмов (ЛСА) – это более компактная, но менее наглядная форма представления ГСА. В ЛСА используют:
символы операторных вершин Yj
символы условных вершин Xj
I, I –верхние и нижние стрелки. Верхние стрелки I ставятся после символов условных вершин Xj и их надстрочный индекс I указывает номер нижней стрелки I , к которой надо перейти, если Xj = 0)
W I – безусловный переход, где i - номера переходов к нижней стрелке I.
Для правильной записи ЛСА отметим на ГСА (рис.1) номерами 1, 2 и 3 вершины, к которым подходят более одной стрелки. Перед символами этих вершин в ЛСА ставятся нижние стрелки с отмеченными на ГСА номерами.
Если возникают затруднения при записи ЛСА, можно вводить дополнительные нижние и верхние стрелки и использовать безусловный переход W I.
ЛСА, соответствующая ГСА на рис.1 имеет вид:
Yн 1 X1 1 Y12 Y2 X22 Y4 X33 Y3 3 Yk