Чорней Р.К. Теорія автоматів
Подождите немного. Документ загружается.
1.4. Мiнiмальний автомат. Алгоритм мiнiмiзацiї скiнченного автомата
a
2
×
a
3
×
{a
6
, a
3
}
{a
5
, a
3
}
{a
4
, a
3
}
a
4
× {a
7
, a
5
}
{a
6
, a
3
}
{a
7
, a
3
}
{a
3
, a
2
}
a
5
× {a
5
, a
4
}
{a
6
, a
3
}
{a
4
, a
3
}
{a
7
, a
4
}
{a
5
, a
2
}
a
6
{a
4
, a
2
}
{a
7
, a
5
}
× × × ×
a
7
× {a
5
, a
2
}
{a
6
, a
3
}
{a
3
, a
2
}
{a
4
, a
3
}
{a
7
, a
2
}
{a
4
, a
2
}
{a
4
, a
2
}
{a
5
, a
4
}
×
a
1
a
2
a
3
a
4
a
5
a
6
Рис. 1.9. Таблиця перетворень для мiнiмiзацiї автомату A (перший крок)
У таблицi на рис. 1.9 потрiбно закреслити клiтинки для пар станiв {a
3
, a
2
},
{a
4
, a
3
}, {a
5
, a
3
}, {a
7
, a
3
}, оскiльки вони мiстять пару {a
6
, a
3
}.
Пiсля цього таблиця набирає вигляду, зображеного на рис. 1.10.
a
2
×
a
3
× ×
a
4
× {a
7
, a
5
} ×
a
5
× {a
5
, a
4
} ×
{a
7
, a
4
}
{a
5
, a
2
}
a
6
{a
4
, a
2
}
{a
7
, a
5
}
× × × ×
a
7
× {a
5
, a
2
} ×
{a
7
, a
2
}
{a
4
, a
2
}
{a
4
, a
2
}
{a
5
, a
4
}
×
a
1
a
2
a
3
a
4
a
5
a
6
Рис. 1.10. Таблиця перетворень для мiнiмiзацiї автомату A (другий крок)
Таблиця на рис. 1.10 вiдповiдає етапу побудови розбиття Q
2
на класи 2-
невiдрiзнюваностi, а також таблицi розбиття Q
2
.
У цiй таблицi знову закреслимо всi тi клiтинки, якi мiстять пари станiв, що вiд-
повiдають закресленим клiтинкам. Отримуємо таблицю розбиття Q
3
i т. д. Процес
завершиться, коли отримано таблицю, в якiй не можна закреслити жодної клiтинки.
У нашому прикладi таку властивiсть має остання з наведених таблиць. Усi неза-
кресленi клiтинки цiєї таблицi вiдповiдають парам невiдрiзнюваних станiв.
Для автомата A маємо такi пари невiдрiзнюваних станiв: {a
6
, a
1
}, {a
4
, a
2
}, {a
5
, a
2
},
{a
7
, a
2
}, {a
5
, a
4
}, {a
7
, a
4
} i {a
7
, a
5
}. Оскiльки вiдношення невiдрiзнюваностi транзи-
тивне, одержуємо класи невiдрiзнюваностi {a
1
, a
6
} i {a
2
, a
4
, a
5
, a
7
}. Кожний стан, що
11
Роздiл 1. Теорiя автоматiв
не ввiйшов у жодний з побудованих класiв невiдрiзнюваностi, не має еквiвалентних
серед станiв розглянутого автомата й утворює одноелементний клас невiдрiзнювано-
стi. Додаючи цi класи, одержуємо шукане розбиття Q.
Остаточно для автомата A маємо Q =
©
{a
1
, a
6
}, {a
2
, a
4
, a
5
, a
7
}, {a
3
}
ª
.
Очевидно, що, реалiзуючи описану процедуру послiдовного закреслення клiтинок
таблицi, не обов’язково на кожному кроцi перемальовувати одержану таблицю, а
можна здiйснювати черговий етап безпосередньо для клiтинок вихiдної таблицi.
1.5. Двi моделi скiнченних автоматiв: автомат Мiлi
та автомат Мура
Скiнченний автомат називається автоматом Мура, якщо його функцiя виходiв
λ залежить тiльки вiд стану i не залежить вiд вхiдного сигналу, тобто для будь-яких
x
0
, x
00
∈ X i a ∈ U виконується рiвнiсть λ(a, x
0
) = λ(a, x
00
).
Вилучивши фiктивну змiнну, функцiю виходiв автомата Мура природно вважати
унарною функцiєю типу U → Y . Традицiйно ця функцiя називається функцiєю
вiдмiток i позначається µ, оскiльки кожному становi a вона ставить у вiдповiднiсть
вiдмiтку — вихiдний сигнал y = µ(a).
Розглянута ранiше модель скiнченного автомата називається автоматом Мiлi.
Безпосередньо з означення випливає, що автомат Мура є окремим випадком автомата
Мiлi.
Способи задання автоматiв Мура є модифiкацiєю вiдповiдних способiв задання
автоматiв Мiлi.
Так, замiсть двох таблиць автомата Мiлi для задання автомата Мура використо-
вують одну таблицю, яку називають вiдмiченою таблицею переходiв. Вiдмiчена
таблиця переходiв — це звичайна таблиця переходiв для функцiї δ, в якiй додатково
записують ще один рядок над рядком станiв a
1
, a
2
, ..., a
s
. У цьому рядку над кожним
станом a
i
записують вихiдний сигнал — значення µ(a
i
) функцiї вiдмiток для стану a
i
.
У графi автомата Мура вихiдний сигнал записують не на дугах, а бiля вершини.
Вершина, що вiдповiдає стану a
i
, позначається вихiдним сигналом µ(a
i
).
Нарештi, матрицi переходiв автомата Мура утворюються так само, як i для авто-
мата Мiлi, а замiсть системи матриць виходiв використовується одна s × n-матриця
W , елемент w
ij
якої дорiвнює одиницi, якщо y
i
= µ(a
i
), i дорiвнює нулю в iншому
випадку.
Наприклад, автомат дорожнього руху D з прикладу 1.1.1 можна перетворити в
автомат Мура. Вiдмiчену таблицю переходiв, граф i матрицю виходiв автомата D
подано на рис. 1.11.
Поняття розширеної функцiї переходiв залишається для автоматiв Мура таким
самим, як i для автоматiв Мiлi. Дещо змiнюється друге зi спiввiдношень (1.3) в
означеннi автоматного вiдображення, набираючи вигляду
ϕ
A
(px) = ϕ
A
(p)µ
¡
δ
?
(a
1
, px)
¢
. (1.6)
Потребують також уточнення поняття гомоморфiзму, iзоморфiзму та невiдрiзню-
ваностi (еквiвалентностi) станiв для автомата Мура.
12
1.5. Двi моделi скiнченних автоматiв: автомат Мiлi та автомат Мура
µ y
1
y
2
y
3
y
4
y
3
y
4
δ a
1
a
2
a
3
a
4
a
5
a
6
x
1
a
2
a
1
a
4
a
2
a
6
a
1
x
2
a
3
a
5
a
4
a
2
a
6
a
1
a
3
/y
3
x
1
²²
x
2
²²
a
1
/y
1
x
2
oo
x
1
²²
a
6
/y
4
x
2
oo
x
1
oo
a
4
/y
4
x
2
//
x
1
//
a
2
/y
2
x
1
OO
x
2
//
a
5
/y
3
x
2
OO
x
1
OO
W =
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
0 0 1 0
0 0 0 1
Рис. 1.11. Вiдмiчена таблиця переходiв, граф i матриця виходiв автомата
дорожнього руху
Так, в означеннi гомоморфiзму (iзоморфiзму) для автоматiв Мура A
1
i A
2
другу
умову з (1.4) необхiдно замiнити на умову
µ
1
(a) = µ
2
¡
γ(a)
¢
.
Стан a
i
∈ U
1
автомата Мура A = (X, Y, U
1
, δ
1
, µ
1
) i стан b
j
∈ U
2
автомата Мура
B = (X, Y, U
2
, δ
2
, µ
2
) називають невiдрiзнюваними, якщо для довiльного вхiдного
слова p ∈ X
?
виконується ϕ
i
A
(p) = ϕ
j
B
(p) i, крiм того, µ
1
(a
i
) = µ
2
(b
j
). Пiсля цього уто-
чнення поняття невiдрiзнюваностi (еквiвалентностi) автоматiв Мура i мiнiмального
автомата Мура формулюють так само, як i для автоматiв Мiлi.
Нескладної модифiкацiї потребує й алгоритм мiнiмiзацiї автоматiв. А саме слiд
увести поняття 0-невiдрiзнюваностi, вважаючи стани a
i
i a
j
автомата Мура A 0-
невiдрiзнюваними, якщо µ(a
i
) = µ(a
j
). Вiдтак на першому кроцi мiнiмiзацiї автомата
Мура множину станiв U автомата A необхiдно розбити на класи 0-невiдрiзнюваностi.
Подальшi кроки алгоритму не змiнюються.
Для довiльного автомата Мiлi iснує еквiвалентний йому автомат Мура B. Сфор-
мулюємо алгоритм побудови автомата B.
Нехай задано автомат Мiлi A = (X, Y, U, δ, λ) i X = {x
1
, x
2
, ..., x
m
} та
U = {a
1
, a
2
, ..., a
s
}. Означимо автомат Мура B = (X, Y, W, δ
0
, µ) таким чином. Мно-
жиною станiв автомата B є W =
©
(a
i
, x
j
) | a
i
∈ U, x
j
∈ X
ª
∪ U, тобто W = U × X ∪ U.
Стан (a
i
, x
j
множини W позначимо як b
ij
, а як b
i0
— стан a
i
∈ U ⊆ W . Функцiю
переходiв δ
0
автомата B для стану b
ij
∈ W i вхiдного символу x
l
∈ X означимо
так:
1) якщо j = 0, тобто b
i0
= a
i
, то δ
0
(b
i0
, x
l
) = b
il
= (a
i
, x
l
);
2) якщо j 6= 0, тобто b
ij
= (a
i
, x
j
), то δ
0
(b
ij
, x
l
) = b
kl
= (a
k
, x
l
), де a
k
= δ(a
i
, x
j
),
тобто δ
0
¡
(a
i
, x
j
), x
l
¢
= δ
¡
(a
i
, x
j
), x
l
¢
.
Функцiю вiдмiток µ для станiв b
i0
можна означити довiльно, а для решти станiв
(j 6= 0) µ(b
ij
) = λ(a
i
, x
j
).
Стан a
i
∈ U автомата Мiлi A i стан b
i0
∈ W автомата Мура B будуть невiдрiзню-
ваними, тобто для довiльного вхiдного слова p ∈ X
?
ϕ
i
A
(p) = ϕ
i0
B
(p).
13
Роздiл 1. Теорiя автоматiв
1.6. Аналiз i синтез автоматiв-перетворювачiв
За зовнiшнiми умовами функцiонування розрiзняють два типи поведiнки i два
вiдповiднi типи скiнченних автоматiв.
Перший тип поведiнки — це розглянуте ранiше перетворення вхiдних слiв у ви-
хiднi слова, тобто реалiзацiя автоматних вiдображень. автомати, якi реалiзують за-
значений тип поведiнки, називають автоматами-перетворювачами.
Другий тип поведiнки — це розпiзнавання певних множин вхiдних слiв. За допо-
могою автомата-розпiзнавача, або автомата-акцептора для будь-якого вхiдного
слова p можна визначити, належить це слово певнiй множинi чи нi. У разi позитивної
вiдповiдi на поставлене питання кажуть, що слово p розпiзнається, або сприймається,
автоматом. В iншому випадку вважають, що слово p не розпiзнається, або вiдкида-
ється.
Основними проблемами теорiї автоматiв для кожного з типiв поведiнки i типiв
автоматiв є проблеми аналiзу i синтезу.
Проблема аналiзу полягає в тому, щоб за заданим автоматом визначити йо-
го поведiнку i дослiдити певнi властивостi цiєї поведiнки. Як правило, розв’язання
проблеми аналiзу принципових труднощiв не викликає, оскiльки звичайно разом iз
заданням автомата наводяться правила опису його поведiнки.
У задачi синтезу необхiдно, виходячи iз заданих умов поведiнки побудувати
(синтезувати) автомат, який реалiзує цю поведiнку. Очевидно, однiєю з перших про-
блем, якi виникають при розв’язаннi задачi синтезу, є дослiдження питання, якi з
умов поведiнки взагалi можуть бути реалiзованi в автоматах i, зокрема, в скiнчен-
них автоматах. Вiдтак постає проблема побудови власне алгоритму синтезу.
Нехай задано автоматне вiдображення ϕ: X
?
→ Y
?
. Для довiльного вхiдного сло-
ва p ∈ X
?
означимо вiдображення ϕ
p
: X
?
→ Y
?
, яке називатимемо залишковим
вiдображенням для вiдображення ϕ
p
(p
0
) = q. Iншими словами, результат зали-
шкового вiдображення ϕ
p
для довiльного вхiдного слова p
0
∈ X
?
можна одержати,
утворивши слово p
00
= pp
0
, визначивши вихiдне слово ϕ(p
00
) i вiдкинувши в ньому
початковий вiдрiзок довжиною |p|.
Позначимо як Φ множину всiх залишкових вiдображень для заданного автома-
тного вiдображення ϕ. Потужнiсть множини Φ називатимемо вагою автоматного
вiдображення ϕ.
Позначатимемо як η
k
(w) початковий вiдрiзок слова w, який має довжину k,
k = 0, 1, 2, ..., |w|; вважатимемо, що η
0
(w) = e.
1.7. Зображування подiй в автоматах
Розглянемо проблеми аналiзу i синтезу для автоматiв-розпiзнавачiв.
При дослiдженнi автоматiв-розпiзнавачiв зручно користуватися моделлю, яку на-
зивають автоматом без виходiв.
Автомат без виходiв A = (X, U, δ, a
1
, F ) означають так: першi три об’єкти x,
U i δ мають той самий сенс, що й ранiше, a
1
∈ U — початковий стан, F — множина
заключних, або фiнальних, станiв автомата A, F ⊆ U. Далi розглядатимемо без
додаткових застережень iнiцiальнi скiнченнi автомати без виходiв.
14
1.8. Алгебра регулярних подiй
Множину P слiв у вхiдному алфавiтi X, тобто P ⊆ X
?
, називають подiєю, або
мовою, в алфавiтi X.
Подiя P є зображуваною в автоматi A = (X, U, δ, a
1
, F ) (або автомат A зобра-
жує подiю P ), якщо δ
?
(a
1
, w) ∈ F тодi й тiльки тодi, коли w ∈ P.
Кожному автоматовi A = (X, U, δ, a
1
, F ) вiдповiдає зображувана подiя P . Подiю P
зручно iлюструвати за допомогою графа автомата A: подiя P складається з усiх вхi-
дних слiв, вiдповiднi шляхи яких у графi автомата A ведуть з вершини a
1
у вершини
з множини F. Кажуть, що автомат A зображує подiю P .
Подiя P називається зображуваною (в автоматi), якщо iснує автомат A, який
зображує цю подiю. Iншi термiни для цього поняття: множина, або мова, яка визна-
чається, допускається або розпiзнається автоматом.
Можлива ситуацiя, коли a
1
∈ F. У такому разi вважатимемо, що подiї P , зобра-
жуванiй в автоматi A, належить порожнє слово e. Порожнє слово не слiд плутати
з порожньою подiєю. Автомат A зображує порожню подiю, якщо не iснує жодного
вхiдного слова, яке переводить автомат A з початкового стану a
1
у будь-який iз за-
ключних станiв. Порожню подiю позначатимемо за допомогою символу порожньої
множини ∅.
1.8. Алгебра регулярних подiй
Нехай P, P
1
, P
2
⊆ X
?
— подiї в алфавiтi X. Розглянемо три операцiї над подiями,
якi називатимемо регулярними операцiями.
1. Об’єднання подiй P
1
∪ P
2
— це звичайне теоретико-множинне об’єднання.
2. Множення (конкатенацiя) подiй P
1
P
2
— це подiя, яка складається з усiх
слiв w
1
w
2
таких, що w
1
∈ P
1
i w
2
∈ P
2
. Традицiйно операцiя множення подiй вико-
ристовується без спецiального позначення. Для зручностi посилання на цю операцiю
позначатимемо її знаком ·.
3. Iтерацiєю подiї P називається подiя P
?
= {e} ∪ P ∪P
2
∪ ...∪ P
n
∪ ... =
S
∞
n=0
P
n
,
де P
0
позначає подiю e, P
n
— подiю PP...P
| {z }
n раз
.
Як P
+
позначатимемо подiю P
?
\ {e}.
Очевидно, що всi три операцiї є всюди визначеними на множинi подiй в алфавiтi
X. Алгеброю подiй в алфавiтi X називається алгебра E =
β(X
?
), {∪, ·,
?
}
®
, носiєм
якої є множина всiх подiй в алфавiтi X (булеан X
?
), а сигнатура складається з
уведених регулярних операцiй.
Застосовуючи оператор суперпозицiї S для операцiй алгебри E, одержуємо вирази
(формули в алгебрi E), якi задають певнi подiї в алфавiтi X. Для того щоб зменшити
кiлькiсть дужок у виразах, домовимось про такi прiоритети для регулярних опера-
цiй: спочатку виконується iтерацiя, потiм множення i пiсля цього об’єднання. Якщо
необхiдно змiнити встановлений порядок виконання операцiй, використовуватимемо
дужки.
Вирази в алгебрi E називають рiвносильними (еквiвалентними), якщо вони за-
дають ту саму подiю. Рiвносильнiсть виразiв позначають знаком =.
15
Роздiл 1. Теорiя автоматiв
Подiї {x
i
}, де x
i
∈ X, називають елементарними. До елементарних подiй нале-
жить також подiя {e}.
Подiя P називається регулярною, якщо вона є результатом застосування скiн-
ченного числа операцiй об’єднання, множення та iтерацiї до елементарних подiй.
Бiльш точно, iндуктивне означення регулярних подiй таке:
1) елементарнi подiї {e} i x
i
, x
i
∈ X, i = 1 , 2, ..., m є регулярними;
2) якщо P
1
i P
2
— регулярнi подiї, то подiї P
1
∪ P
2
, P
1
P
2
i P
?
1
також регулярнi;
3) iнших регулярних подiй, нiж побудованi за правилами 1) i 2), немає.
Як R позначимо клас (множину) усiх регулярних подiй в алфавiтi X. Очевидно,
клас R замкнений вiдносно всiх трьох регулярних операцiй. Отже, можна розгля-
нути алгебру E
R
=
R, {∪, ·,
?
}
®
, яка називається алгеброю регулярних подiй i є
пiдалгеброю алгебри подiй E.
З означення випливає також, що кожна регулярна подiя зображується (задається)
деяким виразом (формулою), що складається зi скiнченного числа регулярних опе-
рацiй. Такi вирази називають регулярними виразами. Регулярним виразом для
порожньої подiї вважатимемо символ ∅.
Регулярнi вирази називають рiвносильними (еквiвалентними), якщо вони зада-
ють ту саму регулярну подiю.
1.9. Подiї i джерела
Граф називається вiдмiченим, якщо його ребрам поставленi у вiдповiднiсть сим-
воли з деякого алфавiту X. Нагадаємо, називається мультиграфом, якщо пари його
вершин можуть бути з’єднанi бiльш нiж одним ребром; цi ребра називають кратними.
Крiм того, вважатимемо, що мультиграф може мiстити петлi.
Джерелом над алфавiтом X називають вiдмiчений орiєнтований мультиграф, в
якому:
1) видiлено початковi й заключнi вершини (вершина може бути одночасно i поча-
тковою, i заключною);
2) кожна дуга позначається або символом з алфавiту X, або порожнiм символом
e (такi дуги називають порожнiми).
Кожне джерело D однозначно визначає подiю P в алфавiтi X, яка складається зi
слiв в алфавiтi X, що вiдповiдають усiм шляхам, якi ведуть з початкових вершин у
заключнi. Якщо шлях мiстить порожню дугу, то йому вiдповiдає слово p
1
ep
2
= p
1
p
2
.
Кажуть, що джерело D зображує подiю P .
Джерела називають рiвносильними (еквiвалентними), якщо вони зображують ту
саму подiю.
Для будь-якої регулярної подiї P iснує двополюсне джерело, яке зображує по-
дiю P .
Твердження можна довести iндукцiєю за означенням регулярної подiї.
1. База iндукцiї. Елементарну подiю зображує джерело, що складається з двох
вершин — початкової та заключної — i дуги мiж ними, вiдмiченої символом цiєї
подiї: x
i
∈ X, i = 1, 2, ..., m або e.
16
1.10. Синтез автоматiв-розпiзнавачiв
2. Крок iндукцiї. Припустимо, що побудовано двополюснi джерела D
1
i D
2
, якi
зображують регулярнi подiї вiдповiдно P
1
i P
2
; початковими вершинами D
1
i D
2
є v
(1)
0
i v
(2)
0
, а заключними — вiдповiдно v
(1)
F
i v
(2)
F
. Тодi джерело D з початковою вершиною
v
0
i заключною вершиною v
F
, що зображує подiю P — результат регулярної операцiї
над подiями P
1
i P
2
, будується так, як показано на рис. 1.12.
v
(1)
0
D
1
v
(1)
F
e
##
G
G
G
G
G
G
G
G
G
G
v
0
e
;;
x
x
x
x
x
x
x
x
x
x
e
##
F
F
F
F
F
F
F
F
F
F
v
F
v
(1)
0
D
1
v
(1)
F
e
//
v
(2)
0
D
2
v
(2)
F
v
(1)
0
D
1
v
(1)
F
e
¶¶
v
(2)
0
D
2
v
(2)
F
e
;;
w
w
w
w
w
w
w
w
w
w
а) б) в)
Рис. 1.12. Побудова регулярних операцiй
1) Для P = P
1
∪ P
2
джерело D називають «паралельним з’єднанням» D
1
i D
2
(рис. 1.12, а). Воно складається з джерел D
1
i D
2
та нових вершин v
0
i v
F
:
з v
0
проводять порожнi дуги в v
(1)
0
i v
(2)
0
, а з v
(1)
F
i v
(2)
F
— порожнi дуги у
вершину v
F
.
2) Для P = P
1
P
2
джерело D будуємо «послiдовним з’єднанням» D
1
i D
2
(рис. 1.12, б ). З v
(1)
F
проводимо порожню дугу у v
(2)
0
. Для джерела D по-
чатковою вершиною v
0
є v
(1)
0
, заключною вершиною v
F
є v
(2)
F
.
3) Якщо P = P
?
1
, то для побудови D проведемо в D
1
порожню дугу з v
(1)
F
у
v
(1)
0
(рис. 1.12, в). Вершина v
(1)
0
є одночасно початковою v
0
i заключною v
F
вершиною джерела D.
1.10. Синтез автоматiв-розпiзнавачiв
Джерело, яке може бути iнтерпретовано як граф якогось iнiцiального скiнченного
автомата без виходiв, тобто джерело, що має єдину початкову вершину, не мiстить
порожнiх дуг i з кожної вершини якого виходить точно m дуг, позначених символами
x
1
, x
2
, ..., x
m
алфавiту X, називається детермiнованим джерелом.
Для довiльного джерела D з n вершинами iснує рiвносильне йому детермiноване
джерело D
0
, яке має не бiльше нiж 2
n
вершин. Опишемо алгоритм побудови джерела
D
0
, або процедуру детермiнiзацiї джерела D.
Множина W ⊆ V вершин джерела D називається замкненою, якщо з того,
що v ∈ W й iснує порожня дуга з v у v
0
, випливає, що v
0
∈ W . Очевидно, що
для джерела без порожнiх дуг будь-яка пiдмножина множини його вершин буде
замкненою. Позначимо як Q
0
найменшу замкнену множину вершин джерела D, яка
мiстить усi початковi вершини D.
Шукане детермiноване джерело D
0
будуємо в такий спосiб.
Утворимо всi замкненi пiдмножини Q
i
множини V вершин джерела D (їх кiль-
кiсть не перевищує 2
n
— кiлькостi елементiв булеана B(V )) i кожнiй такiй пiдмножинi
17
Роздiл 1. Теорiя автоматiв
поставимо у вiдповiднiсть вершину D
0
. Початковою вершиною D
0
вважатимемо Q
0
,
а заключними вершинами D
0
— усi тi пiдмножини Q
i
, якi мiстять принаймнi одну iз
заключних вершин джерела D.
Утворивши вершини джерела D
0
, означимо його дуги.
Якщо Q
j
— найменша замкнена множина, що мiстить усi вершини, в якi з вершин
множини Q
j
у джерелi D ведуть дуги з вiдмiткою x
l
∈ X, то у джерелi D
0
проведемо
дугу з Q
i
у Q
j
i позначимо її символом x
l
. Якщо ж з усiх вершин множини Q
i
у
джерелi D не виходить жодної дуги з вiдмiткою x
l
, то в D
0
проведемо дугу з вiдмi-
ткою x
l
з вершини Q
i
у вершину ∅, яка вiдповiдає порожнiй пiдмножинi множини
вершин V . Таким чином, у джерелi D
0
для кожної вершини Q
i
i кожного символу
x
l
алфавiту X iснує рiвно одна дуга, що виходить з Q
i
, i, отже, D
0
— детермiноване
джерело. Iншими словами, D
0
є графом iнiцiального скiнченного автомата без ви-
ходiв A = (X, U, δ, Q
0
, F ). Описана процедура побудови дуг у D
0
визначає функцiю
переходiв автомата A:
δ(Q
i
, x
l
) = Q
j
.
Для будь-якої регулярної подiї P iснує скiнченний автомат, який зображує цю
подiю.
Побудова (синтез) шуканого автомата починається з побудови джерела D, яке
зображує подiю P , за методом, запропонованим у попередньому пiдроздiлi. Вiдтак
джерело D детермiнується за допомогою описаної вище процедури. На будь-якому з
цих крокiв можна застосувати рiвносильнi перетворення для можливого спрощення
джерела. У пiдсумку синтезований автомат може мати менше нiж 2
n
станiв.
Приклад 1.10.1. Побудуємо скiнченний автомат, який зображує регулярну по-
дiю P , задану регулярним виразом
¡
{x
1
}{x
2
}
?
∪ {x
3
}
¢¡
{x
1
} ∪ {x
2
}{x
3
}
¢
?
{x
2
}{x
1
}
?
.
Спочатку будуємо джерело D, що зображує подiю P , за методом, наведеним у
попередньому пiдроздiлi (рис. 1.13). При цьому деякi «зайвi» порожнi дуги вилучено.
Вершина 1 є початковою, а вершина 8 — заключною.
2
e
&&
M
M
M
M
M
M
M
M
M
M
M
M
M
x
2
§§
5
e
&&
M
M
M
M
M
M
M
M
M
M
M
M
M
1
x
1
88
q
q
q
q
q
q
q
q
q
q
q
q
q
x
3
&&
M
M
M
M
M
M
M
M
M
M
M
M
M
4
x
2
²²
x
1
88
q
q
q
q
q
q
q
q
q
q
q
q
q
x
2
&&
M
M
M
M
M
M
M
M
M
M
M
M
M
7
e
oo
3
e
88
q
q
q
q
q
q
q
q
q
q
q
q
q
6
x
3
88
q
q
q
q
q
q
q
q
q
q
q
q
q
8
x
1
ee
Рис. 1.13. Джерело D, що зображує подiю P
Згiдно з алгоритмом побудоване джерело детермiнується. При цьому розглядаємо
тiльки тi пiдмножини вершин джерела D, якi досяжнi з початкової вершини {1}.
Таблицю функцiй переходiв δ детермiнованого джерела D
0
, вершинами якого є
пiдмножини вершин джерела D, подано на рис. 1.14, а. Оскiльки така таблиця у
18
1.11. Аналiз автоматiв-розпiзнавачiв. Теорема Клiнi
процесi її побудови «росте» за рахунок збiльшення кiлькостi станiв, то зручно по-
мiняти в нiй мiсцями рядки i стовпчики. Пiсля позначення отриманих пiдмножин
символами з алфавiту U = {a
i
, i = 1, 2, ..., s} таблиця переходiв для D
0
набирає
звичайного вигляду таблицi переходiв iнiцiального скiнченного автомата без вихо-
дiв A = (X, U, δ, a
1
, F ) (рис. 1.14, б ). Множина заключних станiв автомата A скла-
дається зi станiв (пiдмножин), якi мiстять заключну вершину 8 джерела D, тобто
F = {a
5
, a
6
, a
7
, a
9
}.
δ x
1
x
2
x
3
δ x
1
x
2
x
3
{1} {2, 4} ∅ {3, 4} a
1
a
2
a
10
a
3
{2, 4} {4, 5, 7} {2, 4, 6, 8} ∅ a
2
a
4
a
5
a
10
{3, 4} {4, 5, 7} {6, 8} ∅ a
3
a
4
a
6
a
10
{4, 5, 7} {4, 5, 7} {6, 8} ∅ a
4
a
4
a
6
a
10
{2, 4, 6, 8} {4, 5, 7, 8} {2, 4, 6, 8} {4, 7} a
5
a
7
a
5
a
8
{6, 8} {8} ∅ {4, 7} a
6
a
9
a
10
a
8
{4, 5, 7, 8} {4, 5, 7, 8} {6, 8} ∅ a
7
a
7
a
6
a
10
{4, 7} {4, 5, 7} {6, 8} ∅ a
8
a
4
a
6
a
10
{8} {8} ∅ ∅ a
9
a
9
a
10
a
10
∅ ∅ ∅ ∅ a
10
a
10
a
10
a
10
а б
Рис. 1.14. Таблицi переходiв i виходiв iнiцiального автомата без виходiв A
1.11. Аналiз автоматiв-розпiзнавачiв. Теорема Клiнi
Будь-яка подiя, зображувана у скiнченному автоматi, є регулярною.
Опишемо iндуктивну процедуру (алгоритм Мак-Нотона — Ямади) побудови
регулярного виразу для подiї, що зображується в заданому скiнченному автоматi
A = (X, U, δ, a
1
, F ), U = {a
1
, a
2
, ..., a
s
}.
Для довiльного вхiдного слова w ∈ X
?
стани δ
?
¡
a
i
, η
k
(w)
¢
, k = 1, 2, ..., |w| − 1
називатимемо промiжними, де через η
k
(w) позначено початковий вiдрiзок слова w
довжини k, 0 6 k 6 |w|; вважатимемо, що η
0
(w) = e.
Позначимо як P
(k)
ij
подiю, що складається з усiх вхiдних слiв w, якi переводять
автомат A зi стану a
i
у стан a
j
, i таких, що промiжними станами для слова w можуть
бути тiльки стани з iндексами, що не перевищують k, тобто тiльки стани з множини
{a
1
, a
2
, ..., a
k
}.
Для k = 0 подiя P
(0)
ij
складається з усiх слiв, якi переводять автомат з a
i
в a
j
i не мають промiжних станiв. Очевидно, такими вхiдними словами є або скiнченна
множина вхiдних сигналiв {x
l1
, x
l2
, ..., x
lr
} таких, що δ(a
i
, x
lt
) = a
j
, t = 1, 2, ..., r, або
порожня множина ∅. Якщо i = j, то e ∈ P
(0)
ij
. Отже, P
(0)
ij
— регулярна подiя. Регу-
лярний вираз для P
(0)
ij
можна одержати безпосередньо з таблицi переходiв автомата
A (i, j = 1 , 2, ..., s).
19
Роздiл 1. Теорiя автоматiв
Для наступних значень k = 1, 2, ... подiї P
(k)
ij
можна обчислити за формулою
P
(k)
ij
= P
(k−1)
ij
∪ P
(k−1)
ik
(P
(k−1)
kk
)
?
P
(k−1)
kj
. (1.7)
Якщо F = {a
j
1
, a
j
2
, ..., a
j
l
}, то подiю P , зображувану автоматом A, можна запи-
сати у виглядi P = P
(s)
1j
1
∪ P
(s)
1j
2
∪ ... ∪ P
(s)
1j
l
(s — кiлькiсть станiв автомата A).
Приклад 1.11.1. Продемонструємо алгоритм Мак-Нотона — Ямади побудови
регулярного виразу для подiї P , зображуваної в автоматi A, граф якого подано
на рис. 1.15. Заключними станами автомата A є a
2
i a
3
, s = 3. Визначимо подiю
P
(3)
12
∪ P
(3)
13
.
a
2
x
2
ww
p
p
p
p
p
p
p
p
p
p
p
p
p
x
1
²²
a
1
x
2
''
N
N
N
N
N
N
N
N
N
N
N
N
N
x
1
((
a
3
x
1
OO
x
2
hh
Рис. 1.15. Автомат A з заключними станами a
2
i a
3
Маємо
P
(0)
11
= e ∪ x
1
, P
(0)
12
= ∅, P
(0)
13
= x
2
,
P
(0)
21
= x
2
, P
(0)
22
= e, P
(0)
23
= x
1
,
P
(0)
31
= ∅, P
(0)
32
= x
1
, P
(0)
33
= e ∪ x
2
.
Одержавши вирази для всiх подiй P
(0)
ij
, i, j = 1, 2, 3, будуємо вирази для P
(1)
ij
,
i, j = 1, 2, 3 за допомогою формули (1.7). Деякi з цих виразiв спрощуємо, користую-
чись тотожностями алгебри регулярних подiй.
P
(1)
11
= e ∪ x
1
∪ (e ∪ x
1
)(e ∪ x
1
)
?
(e ∪ x
1
) = (x
1
)
?
,
P
(1)
12
= ∅ ∪ (e ∪ x
1
)(e ∪ x
1
)
?
∅ = ∅,
P
(1)
13
= x
2
∪ (e ∪ x
1
)(e ∪ x
1
)
?
x
2
=
¡
e ∪ (e ∪ x
1
)(e ∪ x
1
)
?
¢
x
2
=
= (e ∪ x
1
)
?
x
2
= (x
1
)
?
x
2
,
P
(1)
21
= x
2
∪ x
2
(e ∪ x
1
)
?
(e ∪ x
1
) = (x
2
)(x
1
)
?
,
P
(1)
22
= e ∪ x
2
(e ∪ x
1
)
?
∅ = e,
P
(1)
23
= x
1
∪ x
2
(e ∪ x
1
)
?
x
2
= x
1
∪ x
2
(x
1
)
?
x
2
,
P
(1)
31
= ∅ ∪ ∅(e ∪ x
1
)
?
(e ∪ x
1
) = ∅,
P
(1)
32
= x
1
∪ ∅(e ∪ x
1
)
?
∅ = x
1
,
P
(1)
33
= e ∪ x
2
∪ ∅(e ∪ x
1
)
?
x
2
= e ∪ x
2
.
20