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

UptoLike

ВУЗ: 

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

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

Рубрика: 

45
Таблица 3.2
(R
1
) (R
1
, R
2
) (R
1
) (R
2
) ( )
0
1 ∨ 3 ∨ 5 2 ∨ 4 3 ∨ 5
х
у
1 ∨ 3 ∨ 5
2 ∨ 4
1 ∨ 3 ∨ 5
2 ∨ 4
3 ∨ 5
2 ∨ 4
3 ∨ 5
4
3 ∨ 5
4
Таблица 3.3 Таблица 3.4
u w u v z 1 2 3 4 5
1 2 3 4 5 x w w v v v
x 2 2 4 4 4 y u u u z z
y 3 3 3 5 5
Построенные автоматы представляют событие R
1
состояниями 1, 2, 3, а собы-
тие R
2
– состояниями 2, 4. Событие R
1
за вычетом содержащегося в нем пустого слова
представляется также выходными сигналами u и w, а событие R
2
– выходными сиг-
налами v, w. Состоянием 2 или, что то же самое, выходным сигналом w представлено
пересечение событий R
1
и R
2
.
3.3.2. Усовершенствованный основной алгоритм синтеза конечных
автоматов
Рассмотренный выше алгоритм синтеза конечного автомата допускает ряд
уточнений и изменений, позволяющих упрощать синтезируемый автомат.
Первое уточнение преследует цель сократить количество используемых основ-
ных индексов и уменьшить, по возможности, число состояний в синтезируемом ав-
томате.
Рассмотрим понятие комплекс регулярных выражений К, под которым пони-
мается любое конечное множество регулярных выражений R
1
,…,R
p
в одном и том же
конечном алфавите (называемом входным алфавитом комплекса), у которых разме-
чены и снабжены индексами все основные места. При этом различные основные мес-
та в выражениях R
1
,…, R
p
могут иметь один и тот же основной индекс. Всякое мно-
жество, состоящее только из основных мест всех выражений R
1
,…, R
p
, имеющих один
и тот же основной индекс k, называется основным местом комплекса К, при этом
индекс k называется основным индексом этого места. Начальные места всех
выражений R
1
,…, R
p
всегда снабжаются одинаковым индексом 0 и составляют
начальное место комплекса К.
Если некоторое основное место α комплекса K состоит из основных мест
α
1
, α
2
, …, α
k
в выражениях R
1
, …, R
p
, составляющих комплекс, то местами, подчи-
ненными месту
α
в комплексе К, считаются все места в выражениях R
1
, …,R
p,
под-
чиненные хотя бы одному из мест α
1
, …, α
k
в этих выражениях.
Будем считать, что основное место в комплексе K x
i
-следует за предоснов-
ным местом β, если хотя бы одно из составляющих место α основных мест в выраже-
ниях R
1
, …, R
p
x
i
-следует за местом β.
Слово q входного алфавита связывает основное место комплекса К с основ-
ным местом β того же комплекса, если оно связывает некоторое основное место в

Страницы