Основы синтеза и диагностирования автоматов. Воронин В.В. - 195 стр.

UptoLike

ВУЗ: 

ТОГУ | Хабаровск

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

Рубрика: 

191
соответствие между событиями и символами выходного алфавита
(табл. 5.19).
Зная эту таблицу, можно без таблицы
переходов-выходов, найти реакцию автома-
та на любое входное слово. Если множество
событий состоит из конечного достаточного
небольшого числа слов, то его можно задать
простым перечислением слов.
Для представления событий, содержащих бесконечное число
слов, конечными
формулами вводят ряд операций над событиями,
т.е. строят алгебру событий. Эта алгебра включает три операции:
дизъюнкция событий; произведение событий и итерация событий.
Дизъюнкцией событий S
1
, S
2
, …, S
k
называется событие
S = S
1
∨ S
21
∨ S
k
, состоящее из всех слов, входящих в события
S
1
, S
2
, …, S
k
(объединение всех различных слов).
Например, если S
1
={x
1
, x
2
x
1
, x
1
x
1
}, S
2
={x
2
x
2
, x
1
x
2
}, то S
1
∨S
2
={x
1
,
x
2
x
1
, x
1
x
1
, x
2
x
2
, x
1
x
2
}. Пусть события S
1
и S
2
состоят из множества
слов {l
11
, l
12
, l
13
,…} и {l
21
, l
22
, l
23
,…}, соответственно. Произведени-
ем этих событий называется событие S=S
1
S
2
, состоящее из всех слов
вида {l
11
l
21
,l
11
l
22
,l
11
l
23
,…,l
12
l
21
,l
12
l
22
,l
12
l
23
,…,l
13
l
21
,l
13
l
22
,l
13
l
23
,…}.
Результат аналогичен прямому произведению множеств. На-
пример, S
1
S
2
={x
1
x
2
x
2
, x
1
x
1
x
2
, x
2
x
1
x
2
x
2
, x
2
x
1
x
1
x
2
, x
1
x
1
x
2
x
2
, x
1
x
1
x
1
x
2
}. Ана-
логично можно определить произведение большего числа событий.
Операция произведения не коммутативна, т.е. S
1
S
2
≠ S
2
S
1
.
Итерацией события S называется событие {S} (или S*), состоя-
щее из пустого слова l и всех слов вида S, SS, SSS и так далее до
бесконечности.
Например, {S
2
}={l, x
2
x
2
, x
2
x
2
x
2
x
2
, …, x
1
x
2
, x
1
x
2
x
1
x
2
, …, x
1
x
2
…}.
Таблица 5.17
Событие Символ y
i
S
i
(x
1
,…,x
m
)
y
1
S
2
y
2
. . . . . .
S
k
y
k
S
3
—

Страницы