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

UptoLike

ВУЗ: 

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

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

Рубрика: 

39
ходным сигналом) у, называется событием, представленным в автомате
А выходным
сигналом у. Множество, состоящее из событий S
у
, для всех букв выходного алфа-
вита автомата
А, называется каноническим множеством событий данного ав-
томата
А.
2. Каноническое множество событий любого автомата является автоматным
множеством событий. Очевидно и обратное, что для любого автоматного множества
событий M существует такой автомат ( в качестве которого можно выбрать как авто-
мат Мили, так и автомат Мура), каноническое множество событий которого совпада-
ет с множеством M.
В отличие от автоматного отображения абстрактный автомат не определяет-
ся однозначно соответствующим ему каноническим множеством событий, поскольку
одно и тоже автоматное отображение может индуцироваться различными автоматами.
Из рассмотренных определений возникает необходимость решения следующих
важнейших задач абстрактной теории автоматов:
− задачу нахождения по заданному абстрактному автомату
А соответствую-
щего ему канонического множества событий – каноническая задача анализа абст-
рактного автомата;
− обратную задачу, по заданному автоматному множеству событий M нахо-
дить абстрактный автомат, каноническое множество событий которое совпадает
с M – каноническая задача синтеза абстрактного автомата.
3.2.3. Регулярные языки и конечные автоматы
Как отмечалось в п. 3.2.2, любое автоматное отображение ϕ может быть зада-
но конечным множеством М событий во входном алфавите этого отображения. Если
область определения отображения ϕ конечна, то все события множества М конечны.
Конечное событие можно задать, перечислив все его элементы. Ясно, что в случае,
когда область определения отображения ϕ бесконечна, хотя бы одно из событий
множества М также будет бесконечным. Поэтому необходимо разработать специаль-
ный язык, который позволял бы представлять (описывать) бесконечные события, со-
ответствующими конечными выражениями.
Рассмотрим язык регулярных выражений алгебры событий. Для этого исполь-
зуем три операции над событиями:
1) А ∪ В – объединение (дизъюнкция);
2) А ⋅ В – умножение (конкатенация);
3) {A} – итерация (обозначается также А*).
Определим конечные множества входных букв Х = {x
1
, ..., x
n
} и зададим для
этого множества регулярное выражение.
Регулярным выражением в алфавите Х называется выражение, построенное из
букв алфавита Х и из символов операций объединения, умножения и итерации с ис-
пользованием соответствующим образом круглых скобок. Всякое регулярное выра-
жение определяет некоторое событие S (S получается в результате выполнения всех
операций, входящих в регулярное выражение). События, определяемые таким обра-
зом, называются регулярными событиями над алфавитом Х. Другими словами регу-
лярным событием (или языком) называется событие, полученное из элементарных
событий (однобуквенных слов
x
i
) применением конечного числа раз операций дизъ-
юнкции, конкатенации и итерации. Например, в алфавите из трех букв x, y, z регуляр-

Страницы