Теория алгоритмов и формальных языков. Мелихов А.Н - 68 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

Теореме 3.1. Задание частичного автоматного отображения f множества
*
x
V в
*
y
V
произвольного автомата
A
с входным алфавитом
{
}
mx
xxxV ,,,
21
K
=
и выходным
алфавитом
{}
ny
yyyV ,,,
21
K= эквивалентно заданию канонического множества событий
n
PPP ,,,
21
K данного автомата.
Доказательство. Вначале покажем, что задание f однозначно определяет
каноническое множество событий автомата
A
.
Пусть f - частичное автоматное отображение
*
x
V в
*
y
V и
α
- произвольное слово
из
*
x
V . Если образ )(
α
f существует и оканчивается буквой
j
y . Если хотя бы для одной
входной буквы слова
α
не определена выходная буква, то слово
α
является
запрещенным и его относим к множеству
R
- области запрета автомата A . Легко видеть,
что в результате просмотра всех слов
*
x
V∈
α
множеств
*
x
V разбивается на 1+n попарно
непересекающихся подмножества
n
PPP ,,,
21
K являются событиями, представленными в
автомате выходными сигналами
n
yyy ,,,
21
K , и образуют каноническое множество
событий автомата A , а множество
R
- событие, состоящее из всех тех слов
*
x
V∈
α
,
которые не вошли ни в одно из событий IjP
j
∈
,.
Покажем теперь, что задание канонического множества событий автомата
A
однозначно задает частичное отображение f ,индуцируемое автоматом A . Пусть дано
каноническое множество событий
n
PPP ,,,
21
K автомата
A
, Покажем, каким образом
определить отображение f не прибегая к помощи переходов и выходов автомата A .
Предположим, что
ikii
xxx ,,,
21
K
=
α
- произвольное входное слово из
*
x
V . Для каждого
)1( klx
il
≤≤ найдем выходную букву
jl
y по следующему правилу:
jl
y есть выходной
сигнал, представляющий в автомате A событие
jl
P , которое содержит начальный отрезок
illl
xxx ,,,
21
K длины l входного слова
α
. Если для всех kl ,,2,1 K
=
уществует
соответствующие им
jl
y , то полагаем
jkjjikii
yyyxxxfPf ,,,),,,()(
2121
KK
=
=
.Если хотя
бы для одного
l не существует
jl
y , то полагаем, что отображение f на слове
α
не
определено
R
P ∈
. Этим теорема доказана.
Таким образом из теоремы 3.1 вытекает, что произвольные автоматные
отображения можно задавать с помощью разбиений множества
*
x
V всех слов во входном
алфавите на конечное число попарно непересекающихся событий. Для эффективного
описания конечных и некоторых классов бесконечных событий рассмотрим так
называемую алгебру (регулярных) событий, предложенную С. Клини.
Алгеброй событий в алфавите
x
V называется множество всех событий в этом
алфавите, на котором задана система трех операций: дизъюнкции (v), умножения(
•
) и
итерации (
{}
*
), которые определяются следующим образом.
Событие
P
, равное дизъюнкции событий
21
vPP , определяется как множество слов,
принадлежащих событиям
1
P или
2
P
Событие
R
, равное умножению
21
RR
, определяется как конкатенация
(приписывание справа) к любому слову события
1
R любого слова события
2
R .
Итерацией события
P
по определению является множество всех слов, которые
могут быть получены по следующей формуле:
{}
KKK PvPPvPvPPvPPPvP
λ
=
*
.

Страницы