Синтез цифровых автоматов. Захаров Н.Г - 41 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

40
ное выражение x {x ∨ y ∨ z} (y ∨ z) задает регулярное событие, состоящее из всех
слов, которые начинаются буквой х и заканчиваются буквой y или z. Для конечных
автоматов характерны только регулярные события.
Таким образом, общая задача анализа абстрактного автомата ставится как зада-
ча нахождения по заданному абстрактному автомату такого события, которое пред-
ставлено любым множеством его состояний. Аналогично, общая задача синтеза абст-
рактного автомата ставится как задача построения по любому конечному множеству
М событий такого автомата, который представляет каждое событие этого множества
некоторым множеством своих выходных сигналов.
3.3. Алгоритм синтеза конечных автоматов
Рассмотренный выше стандартный прием позволяет свести общую задачу син-
теза автоматов к канонической задаче. При решении этой задачи необходимо, с одной
стороны, фиксировать некоторый язык, приспособленный для конструктивного опи-
сания событий, а с другой стороны – ограничиться вполне определенным классом ав-
томатов, допускающих какой-либо конструктивный способ задания. Поэтому ограни-
чимся лишь конечными автоматами и регулярными событиями. Оба эти класса объ-
ектов допускают конструктивное описание: первый – на языке таблиц переходов и
выходов, а второй – на языке регулярных выражений алгебры событий. Такое
ограничение вполне достаточно для практических целей, потому что цифровые
автоматы, с которыми приходится иметь дело на практике, всегда конечны.
3.3.1. Основной алгоритм синтеза конечных автоматов
Пусть требуется построить алгоритм, который позволял бы по любому конеч-
ному множеству М регулярных событий, заданных своими регулярными выражения-
ми, находить таблицу переходов и выходов конечного вполне определенного автома-
та Мили и отмеченную таблицу переходов конечного вполне определенного автома-
та Мура А таких, что все события множества M представляются как в автомате Мили,
так и в автомате Мура некоторыми множествами их выходных сигналов.
Перейдем от представления событий R
1
, ..., R
p
в автомате Мура множествами
состояний к представлению их множествами выходных сигналов. Для этого доста-
точно в качестве выходных сигналов взять различные подмножества заданного мно-
жества событий (R
1
,…,R
p
) и отмечать каждое состояние q автомата множеством тех
событий, которые содержат слова, переводящие автомат из начального состояния в
состояние q.
Если состояния, не представляют ни одного из заданных событий, то они от-
мечаются пустым множеством событий. Такой способ отметок состояний автомата
Мура называется каноническим способом отметок.
Если исходные для алгоритма регулярных выражений R
1
,…, R
p
заданные регу-
лярные события являются многочленами, то они заключаются в обычные (неитераци-
онные) скобки. Это условие будет называться условием правильной записи регуляр-
ных выражений.
Местами в правильно записанном регулярном выражении R над алфавитом
X = (x
1
,…, x
n
) условимся называть специально вводимые знаки раздела (вертикаль-
ные линии), ставящиеся между любыми двумя знаками этого выражения (знаками в

Страницы