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

UptoLike

ВУЗ: 

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

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

Рубрика: 

54
отображении) в множество слов в выходном алфавите (конечном алфавите). Отобра-
жения (как правило, частичные), индуцируемые абстрактными автоматами, называ-
ются автоматными отображениями.
Рассмотрим этапы решения задачи синтеза автоматов по индуцируемым ими
отображениям.
Первый этап решения задачи состоит в том, что исходное (частичное) алфа-
витное отображение ϕ записывается в виде таблицы соответствия и приводится к ав-
томатному виду с помощью применения операции выравнивания длин слов (п. 3.2.1).
При этом прежде чем использовать стандартную операцию выравнивания длин слов,
производится ряд последовательных попыток приведения отображения к автоматно-
му виду приписыванием к словам по возможности меньшего числа пустых букв с
проверкой после каждой попытки выполнимости условий автоматности. Резуль-
татом первого этапа является сокращенная таблица соответствия автоматного ото-
бражения ψ, полученная на основе исходного отображения ϕ после применения опе-
рации выравнивания длин слов.
Второй этап решения состоит в нахождении канонического множества со-
бытий, соответствующего отображению ψ. Число событий канонического множества
равно числу букв выходного алфавита Y = (y
1
, ..., y
m
) отображения ψ. Событие S(y
i
)
этого множества, соответствующее выходной букве y
i
, строится следующим образом.
Просматривая сокращенную таблицу соответствия отображения ψ, выделяют все на-
чальные отрезки выходных слов, оканчивающиеся буквой y
i
.
Начальные отрезки входных слов отображения, соответствующие выделенным
отрезкам, и составят событие S(y
i
) (i = 1, ..., m).
Результатом второго этапа является каноническое множество событий
S(y
1
), ..., S(y
m
) отображения ψ. На этом этапе также контролируется правильность вы-
полнения операций первого этапа. Если найденные события попарно не пересекают-
ся, то только тогда отображение ψ считается автоматным.
Третий этап решения состоит в нахождении возможно более простых регу-
лярных выражений для найденных на предыдущем этапе событий S(y
1
), ..., S(y
m
). При
этом используют тождественные преобразования алгебры событий, а также возмож-
ность расширения событий подыскиванием для события S(y
i
) наиболее простого ре-
гулярного выражения и добавлением к нему произвольного множества запрещенных
слов, т. е. таких слов, которые не содержатся ни в одном из исходных событий S(y
1
),
..., S(y
m
). Найденное таким образом регулярное выражение события S(y
i
) для просто-
ты будем обозначать через y
i
(i = 1, ..., m). Отметим, что события, представленные
простыми регулярными выражениями y
1
, ..., y
m
, могут пересекаться между собой.
Результатом третьего этапа является множество М всех найденных регулярных
выражений y
1
, ..., y
m
.
Четвертый этап решения состоит в синтезе конечного автомата Мили или
Мура, представляющего события R
1
, ..., R
m
, задаваемые регулярными выражениями
y
1
, ..., y
m
, посредством множеств своих выходных сигналов. Процесс синтеза может
производиться по двум основным вариантам.
По первому варианту синтеза с естественной областью запрета считаются за-
прещенными, во-первых, все те слова, у которых хотя бы один непустой начальный
отрезок (включая само слово) не содержится ни в одном из событий R
1
, ..., R
m
, и,
во-вторых, все те слова, у которых хотя бы один непустой начальный отрезок (вклю-
чая само слово) содержится одновременно в нескольких (более чем в одном) собы-

Страницы