Дискретна математика

Нехай ми можемо зробити те ж для програми довжиною k - 1. Тоді відомий стан alk 1 і вихідна

послідовність bj1,…,bjk-1Отже ми можемо за допомогою alk = f1(alk-1,eik) і bjk = f2(alk-1,eik) визначити і k-ий вихідний символ.

Нехай нам невідомий початковий стан a0. Якщо автомат нетривіальний, то щонайменше для одного

вхідного символу ei знайдеться пара станів al і ar таких, що f2(al,lir) f2(ap,lir).

А тому можемо зробити висновок, що вихідні послідовності для будь-якої програми ei1,ei2,…,eik для різних початкових станів автомата al і ap різні.

У такий спосіб передбачити поведінку автомата і його реакцію на програму, можна тільки знаючи функції f1 й f2 і початковий стан. У цьому можна переконатися на прикладах 2 і 3, якщо програма починається на 3 і e0 відповідно.

Пізніше ми розглянемо ще одну постановку задачі аналізу, а зараз розглянемо деякі особливості графів і матриць переходів та їх застосування для аналізу скінчених автоматів.

90.Вл стивості гр фів переходів

Ми розглянули раніше граф переходів без паралельних ребер. Якщо існує декілька паралельних ребер ei1/bi1, ei2/bi2 ,…, eir/bir , то їх можна замінити одним ребром, позначеним

(ei1/bi1) (ei2/bi2) … (eir/bir).

Як і для графів, для автоматів важлива досяжність одних вершин із інших.

Визначення. Стан, у який не входить жодна дуга і не виходить жодна дуга, назвемо ізольованим. Стан, у який входить щонайменше одна дуга, але не виходить жодна дуга, назвемо тупиковим. Стан, у який не входить жодна дуга, але виходить, щонайменше, одна дуга, назвемо перехідним.

Позначимо Gk(Ai) множину усіх станів автомата, у які можна потрапити з будь-якого стану

множини Ai при подачі на вхід програми довжиною не більше k . Легко помітити, що G0(Al) = Al, а Gl(Al) - це об'єднання Ai і станів, зазначених у рядках al1,al2,…,alr підтаблиці ai+1 таблиці переходів автомата.

Очевидно G0(Al)=G1(Gk-1(Al)).

Тому, якщо G0(Al) = Gk-1(Al), то G0k+s(Al) = Gk-1(Al) для будь-якого цілого s 1, причому тоді Gk(Al) - це всі стани в який можна потрапити з Al. Цю множину легко встановити. Позначимо її G0(Al). Тоді алгоритм побудови G(Al) включає такі кроки:

1.Приймаємо G0(Al) = Al, k=1.

2.Визначаємо Gk(Al) = G1(Gk-1(Al)).

3.Якщо Gk(Al) Gk-1(Al), то k = k+1 і перехід на крок 2. Інакше G(Al) = Gk(Al) і кінець.

Цікаво розглянути випадок, коли Al містить один елемент al. Назвемо G(al) al-досяжною множиною.

Теорема 5.2. Якщо стан a0 G(al) в автоматі з m станами, то він досяжний з al при подачі на вхід програми довжиною не більш m-1.

Доведення. Воно засноване на алгоритмі побудови G0(Al). Якщо Gk(Al) Gk-1(Al), то Gk(Al) повинно містити щонайменше на один стан більше чим Gk-1(Al). Але в Gk(Al) не може бути більше m станів. Якщо врахувати, що G0(Al) містить уже r станів, то рівність Gk(Al)=Gk-1(Al) повинна бути досягнута при k m-r+1. Тоді G(Al)=Gm-r(Al).

Звідси, оскільки Ai містить лише один стан, то G(al) = Gm-1(al). Це означає, що якщо ap належить ai-досяжній множині, то він досяжний з ai при подачі на вхід програми довжиною m-1 чи менше. Теорема доведена.

Позначимо Hk(Al) множину усіх станів автомата, у які ведуть неорієнтовані шляхи довжини не

більш k зі станів множини Al = {al1,al2,…,alr}. Легко помітити, що H0(Al) = Al, а H1(Al) - це об'єднання Al станів з рядків {al1,al2,…,alr} підтаблиці ai+1 таблиці переходів і станів лівого стовпця таблиці, у рядку яких у підтаблиці ai+1 є будь-який стан з Al. Очевидно:

Hk(Al)=H1(Hk-1(Al)).

Тому Hk+s(Al)=Hk-1(Al) для будь-якого цілого s 1, причому тоді Hk-1(Al) - множина усіх станів, зв'язаних з Al неорієнтовним шляхом довільної довжини.

За аналогією з G(Al) цю множину, яка позначається H(Al), на основі графа переходів можна визначити за допомогою наступного алгоритму:

1.Приймаємо H0(Ai) = Ai, k = 1.

2.Визначаємо Hk(Ai) = H1 (Hk-1 (Ai )).

3.Якщо Hk(Ai) Hk-1 (Ai ), то k = k + 1 і переходимо на крок 2. Інакше, H(Ai) = Hk(Ai) і кінець. Аналогічно можна довести, що буде потрібно не більше ніж m - r повторів кроку 2.

91.М триці переходів т їх вл стивості

Граф переходів можна задати матрицею, що дозволяє більш формально виконувати деякі операції над графами. Ця матриця M = || mip || розмірами n n, де n – кількість станів автомата, називається матрицею

101

переходів. Її елементом mip є позначення ребра, що веде із ai стану в стан ap, якщо таке ребро існує, і нулем в супротивному випадку.

Приклад. Для розглянутого в прикладі 2 автомата матриця має вигляд:

Очевидно, у кожному рядку повинно міститися стільки пар вхід/вихід, скільки є символів у алфавіті Е. За допомогою матриці переходів легко встановити перехідні, тупикові й ізольовані стани. На основі матриці переходів також можна легко визначити множини Gl(Al) і Hl(Al).

Оскільки аналіз автоматів пов‘язаний з визначенням вихідних послідовностей на визначену програму довжини r, то з точки зору графів переходів нас цікавить визначення орієнтованих шляхів і орієнтованих маршрутів зазначеної довжини.

Проведення аналогії між матрицями автоматів і матрицями орграфів, для яких матриці ступеня p містили кількості орієнтованих маршрутів довжиною p між відповідними парами вершин, дозволяє зробити припущення про те, що використання матриць вищих порядків істотно полегшить вирішення проблеми встановлення всіх шляхів і маршрутів між довільними станами автомата.

Дослідження переходів в втом ті з допомогою м триць переходів. Якщо виникає проблема переведення автомата зі стану в стан, то її розв‘язання пов‘язане з аналізом маршрутів у графі переходів автомата. Особливо цікавлять дослідників шляхи і замкнені шляхи в графах переходів. Легко помітити, що якщо автомат має m станів, то довжина шляху не може перевищувати m-1, а довжина замкненого шляху - m.

Маршрут, в якому містяться повторювані стани, назвемо надлишковим маршрутом. Для автомата важливою характеристикою є множина усіх маршрутів і шляхів і, зокрема, надлишкових маршрутів, довжини k між кожною парою станів.

Позначимо Plpk множину усіх маршрутів довжини k зі стану al в стан ap. Очевидно, множина Plpk

порожня і запишемо Plpk 0 , якщо al і ap не пов‘язані жодним ребром у графі переходів, чи Plpk mlp ,

якщо al і ap з‘єднані одним ребром. Нехай P 1 P 1 позначає маршрут з al у ap через aj1 . Тоді один маршрут

lj1 j1l

довжини k може бути представлений у вигляді

а вся множина маршрутів з al у ap довжини k може бути представленf сумою

де кожен елемент – один з маршрутів.

У представленні (5.7), якщо який-небудь зі співмножників дорівнює нулю, то (5.7) також набуває значення 0. Отже, у виразі (5.8) нульові елементи суми розуміємо як неіснуючі маршрути.

Теорема 5.3. Для будь-якого скінченого автомата виконується

s 1

Теорема доведена.

Визначивши всі маршрути довжини k між кожною парою вершин, ми можемо побудувати матрицю переходів k–1-го порядку

Чи можна визначення всіх маршрутів довжини k, тобто визначення матриці переходів, звести до виконання деякої операції над матрицею M?

102

Нехай задані матриці переходів

N = || nlp || m m , D = || dlp || m m .

Тоді визначимо множення матриць переходів N і D як операцію одержання матриці переходів C = || Clp || m m , у якій

s 1

Будемо позначати C=ND.

У (5.10) множення не комутативне, але асоціативне і дистрибутивне щодо суми в (5.8). Легко, таким чином, побудувати для M матрицю M(k). Справедлива наступна

Теорема 5.4. Усі шляхи довжини k зі стану a1 в стан ap будь-якого автомата, заданого матрицею

переходів M задаються елементом alp матриці Mk. Доведення. Легко показати, що M(k+1)=MM(k).

m

По-перше, за означенням множення (5.10) елементом (l, p) множення MM(k) буде p(ls1) psp( k ) .

s 1

По-друге, згідно з теоремою 5.3 це елемент (l, p) у M(k+1). Тепер покажемо індукцією, що M(k) = Mk.

Для k =1 це справедливо за побудовою. Для k нехай, за означенням, M(k) = Mk. Тоді

M(k+1)=MM(k)=MMk. Теорема доведена.

Щоб уникнути визначення в множині Plp( k ) надлишкових шляхів можна використовувати ту

особливість, що будь-який надлишковий маршрут довжини r повинен містити щонайменше один замкнений шлях довжини менше r. А оскільки замкнені шляхи визначаються діагональними елементами, то їх послідовне вилучення, починаючи з матриці M, приведе до того, що в матриці Mk вони будуть відсутні.

Нехай Mopt(k) є матриця M(k), в якій не міститься надлишкових маршрутів, k=1,2,… Теорема 5.5. MMopt(k) містить тільки всі шляхи і замкнені маршрути M(k+1).

Доведення. У MMopt (k) кожен елемент (l,p), l p, містить усі маршрути довжини k+l, отримані приєднанням до кожного маршруту довжини k з al у яке-небудь as ребра з as в ap. Аналогічно, кожен елемент (l,p), l p, містить усі замкнені маршрути довжини k+l. Якщо маршрут довжини k чи ребро, що приєднується, були надлишковими, то маршрут довжини k+l буде також надлишковим. Таким чином, якщо Mopt (k) і Mopt не містять надлишкових маршрутів, відповідно довжини k і l, викреслених нами, то всі шляхи залишаються. Замкнуті шляхи довжини k+l, що утворюються, також залишаються (на діагоналях). Теорема доведена.

Легко запропонувати алгоритм побудови Mopt (k), k = r > l.

1.Будуємо M, вставляючи на діагоналі M нулі, k=l.

2.Будуємо Mopt (k+1) = MMopt (k). Замінюємо всі діагональні елементи нулями. Якщо k + l = r, то результатом є Mopt (k+1), інакше k = k + l і перехід на 2.

92.Н йкоротші т з мкнені шляхи.

Н йкоротші шляхи. Якщо прийняти, що перед дослідником може стояти задача переведення автомата зі стану al у стан ap, то можна далі міркувати так. Зі стану al у стан ap може вести множина Plp(1)

маршрутів довжини 1, Plp( 2) маршрутів довжини 2 і т.д. Природньо вибрати з усіх маршрутів ненадлишкові

маршрути, тобто шляхи. Але можуть існувати шляхи різної довжини. Якщо пов'язати з переведенням зі стану в стан витрати, то досліднику вигідно звернутися до шляху найменшої довжини, тобто найкоротшому шляху. Але якими властивостями володіє шлях найменшої довжини?

Теорема 5.6. Якщо існує найкоротший маршрут зі стану al у стан ap (l p) автомата, то він належить

елементу (l, p) матриці Mopt(k), 1 k m - 1.

Доведення. Оскільки шлях не може пройти через один стан двічі, то, мабуть, він може включати в автоматі зі m станами не більш m – 1 ребер.

По-друге, найкоротший маршрут завжди буде шляхом, так як в маршруті надлишковому завжди можна знайти замкнутий маршрут меншої довжини, виключення якого з надлишкового маршруту робить його коротше.

По-третє, оскільки матриця Mopt(k) не містить надлишкових маршрутів, але містить шляхи, то завдяки тому, що найкоротший маршрут є шляхом, то він належить цій матриці при 1 k m-1. Теорема доведена.

Просто побудувати алгоритм визначення найкоротшого маршруту. Крок 1. k = 1

Крок 2. Будуємо Mopt(k).

Крок 3. Якщо елемент (l, p) у Mopt(k) нульовий, то йдемо на 4, інакше 5.

Крок 4. Якщо k = m – 1, то шляху з al у ap не існує і кінець, інакше k = k + 1, і перехід на крок 2.

103

Крок 5. Шуканий шлях міститься в елементі (l, p).

З мкнені шляхи “довжини” m. Пошук цих шляхів необхідний, якщо потрібно перевірити кожен стан автомата, проходячи через кожен стан лише один раз.

Теорема 5.7. Усі замкнуті шляхи довжини m містяться на головній діагоналі MM(m-1). Доведення. Тому що замкнутий шлях перетворюється в замкнутий шлях приєднанням ребра до шляху

довжиною m – 1 і всі шляхи довжини m – 1 містяться в M(m-1), то MM(m-1) на головній діагоналі містить усі замкнуті шляхи довжини m0.

93.Еквів лентність ст нів

Надалі будемо застосовувати позначення М|a для стислого запису висловлювання «автомат М знаходиться в стані a».

Визначення. Будемо говорити, що стан ai автомата М1 і стан aj автомата М2 еквівалентні, якщо М1|ai і М2|aj під впливом будь-якої вхідної послідовності видають однакові вихідні послідовності. Якщо ai і aj не еквівалентні, то будемо говорити, що вони розрізнені. Позначення М1 і М2 можуть відноситися до того самого автомата.

Таким чином, ai і aj еквівалентні тоді і тільки тоді, коли, спостерігаючи зовнішні виходи, не можна відрізнити автомат М1, що знаходиться в початковому стані ai, від автомата М2, що знаходиться в початковому стані aj. Стани ai і aj розрізнені тоді і тільки тоді, коли є хоча б одна вхідна послідовність, подача якої як на М1, так і на М2. дає на виходах різні послідовності.

Еквівалентність станів ai, і aj позначається рівністю ai = aj. а розрізнення станів ai і aj - нерівністю ai aj. З визначення легко довести, що еквівалентність станів має такі властивості:

1)рефлексивність (ai = ai);

2)симетричність (якщо (ai = aj, то aj = ai);

3)транзитивність (якщо ai = aj і ai = ak, то ai = ak).

Отже, еквівалентність станів може розглядатися як звичайне відношення еквівалентності, що може бути застосованим до множин станів довільної потужності. Розрізненість станів не має властивості рефлексивності і транзитивності і, отже, може відноситися тільки до пар станів.

Наступні леми підтверджують, що в деяких випадках еквівалентність чи розрізнення двох станів того самого автомата можуть бути встановлені дослідженням таблиці переходів даного автомата.

Лема 5.1. Нехай ai і aj - стани автомата М. Якщо рядки ai і aj у підтаблиці zv автомата М розрізняються, то ai aj. Лема доведена.

Доведення. Очевидно, існує принаймні один вхідний символ, при поданні якого на вхід M|ai і до М|aj, на виході М отримаємо різні вихідні символи. Отже, за визначенням, ai aj.

Лема 5.2. Нехай ai і aj - стани автомата М. Якщо рядки ai і aj у повній таблиці переходів автомата М однакові, то ai = aj.

Доведення. При поданні на вхід М|ai і на вхід М|aj, будь-якого вхідного символу вихідні символи і наступні стани в обох випадках будуть однакові. Оскільки М|ai і М|aj переходять у той самий стан, їх реакції на усі підпослідовності вхідних сигналів повинні збігатися. Отже, за означенням ai = aj. Лема доведена.

Лема 3.3. Нехай ai і aj — стани автомата М. Якщо рядки ai і aj повної таблиці переходів автомата М стають однаковими при заміні кожного позначення ai на aj (чи навпаки) то ai = aj.

Доведення. При поданні будь-якого вхідного символу на вхід М|ai і на вхід М|aj вихідні символи однакові і , крім того, щодо наступних станів можливі таких два випадки: або М|ai і М|aj переходять у той самий стан, або в стани ai і aj (не обов‘язково відповідно). Якщо наступний стан той самий, то реакції автомата на вхідні підпослідовності будуть збігатися. Якщо наступними станами є ai і aj, то відновиться вихідна ситуація, і наведені вище міркування можна буде повторити, щоб показати, що наступні вихідні символи однакові в обох випадках. Потім, за індукцією, одержимо, що реакції автомата в станах ai і aj на будь-яку вхідну послідовність будуть однаковими, звідки випливає, що ai = aj. Лема доведена.

Пари рядків, що володіють властивостями, наведеними у лемі 5.1, називаються явно розрізненими, а стани, що стоять в основному стовпці в цих рядках, - явно розрізненими станами. Пари рядків, що володіють властивостями, зазначеними в лемах 5.2 і 5.3, називаються явно еквівалентними, а стани, що стоять в основному стовпці в цих рядках, - явно еквівалентними станами.

Т ким чином, спр ведлив н ступн

Теорема 5.8. Якщо стани ai і aj явно розрізнені, то ai aj, а якщо стани ai і aj явно еквівалентні, то ai = aj. Варто зазначити, що твердження, обернене теоремі 5.8, не виконується, тобто не кожна пара

розрізнених станів є явно розрізненою і не кожна пара еквівалентних станів явно еквівалентна. Можна встановити, що в явно мінімальному автоматі усі пари станів розрізнені, а в явно скоротному автоматі є принаймні одна пара еквівалентних станів. Для ілюстрації лем 5.1 - 5.3 розглянемо автомат M3, представлений графом переходів, зображеним на рисунку 5.3, і таблицею переходів 5.1.

104

(γ/1)

Рис. 5.3. Автом т M3.

З таблиці переходів видно, що рядки 1 і 5 однакові, а рядки 2 і 6 стають однаковими, якщо кожну цифру 2 замінити на цифру 6 (чи кожну цифру 6 замінити на цифру 2). Отже, стани в парах {1,5} і {2,6} є еквівалентними. Розгляд підтаблиці zv показує також, що жодний стан з множини {1,4,5,8} не може бути еквівалентним якому-небудь стану з множини {2,3,6,7}.

Таблиця 5.1 Автомат M3

94.К-еквів лентність

Визначення. Стан ai автомата М1 і стан aj автомата М2 називаються k-еквівалентними, якщо при поданні на вхід M1|ai і М2|aj будь-якої вхідної послідовності довжини k вони виробляють однакові вихідні послідовності. Якщо ai і aj не є k-еквівалентними, то вони називаються k-розрізненими. Позначення М1 і М2 можуть відноситися до того ж самого автомата.

Таким чином, ai і aj є k-еквівалентними тоді і тільки тоді, коли, прикладаючи вхідні послідовності довжини k і спостерігаючи сигнали на зовнішніх виходах, неможливо відрізнити автомат М1 у стані ai від автомата М2 у стані aj. Стани ai і aj є k-розрізненими тоді і тільки тоді, коли є хоча б одна вхідна послідовність довжини k, що при поданні її на вхід М1|ai і М2|aj змушує ці автомати виробляти різні вихідні послідовності. Два 1-розрізнених стани є явно розрізненими.

Легко довести, що відношення k-еквівалентності станів має властивості рефлексивності, симетричності і транзитивності. Отже, k-еквівалентність можна трактувати як звичайне відношення еквівалентності, що безпосередньо застосовне до множин станів будь-якої потужності. З іншого боку, k- розрізнення не має властивостей рефлексивності і транзитивності, і, отже, це поняття застосовне тільки до пар станів.

Лема 5.4. (а) Якщо два стани є k-еквівалентними, то вони є і l-еквівалентними для кожного l k. (б) Якщо два стани є k-розрізненими, то вони є і l-розрізненими для кожного l k.

Доведення. (а) Нехай ai і aj є k-еквівалентними, але розрізненими при деякій вхідній послідовності, скажемо l, довжини l k. Тоді ai і aj повинні бути розрізненими при вхідній послідовності l k-l, де k-l; являє собою будь-яку вхідну послідовність довжини k – l. Отже, ai і aj є k-розрізненими, що суперечить умові.

(б) Нехай ai і aj є k-розрізненими, але l-еквівалентними для деякого l k. Однак, згідно (а), якщо ai і aj є l-еквівалентними, вони повинні бути k-еквівалентними для кожного k l. Отримане протиріччя доводить справедливість твердження (б).

Стан, у яке переходить стан ai, при подачі вхідної послідовності довжини k називається k-м спадкоємцем ai, стосовно цієї послідовності. Нульовим спадкоємцем стану є сам стан.

Теорема 5.9. Якщо стани ai і aj є k-еквівалентними і якщо їхні k-і спадкоємці стосовно будь-якої вхідної послідовності довжини k є еквівалентними, то ai = aj.

Доведення. Якщо ai і aj є k-еквівалентними, то, відповідно до леми 3.4, вони виробляють однакові реакції при усіх вхідних послідовностях довжини k чи менше. Якщо їх k-і спадкоємці стосовно будь-якої вхідної послідовності довжини k є еквівалентними, то вони виробляють однакові реакції для усіх вхідних

105

послідовностей, які слідують за першими k символами. Отже, ai і aj виробляють однакові виходи при вхідних послідовностях будь-якої довжини. Звідси робимо висновок, що ai = aj.

Теорема 5.10. Якщо стани ai і aj є еквівалентними, то їх k-і спадкоємці стосовно будь-якої вхідної послідовності довжини k і для будь-якого k є еквівалентними.

Доведення. Нехай a i і a j є k-ми спадкоємцями станів ai і aj відповідно стосовно довільної вхідної послідовності k. Якщо a i a j, то є послідовність, скажемо l, для якої a i і a j, виробляють різні реакції. Отже, реакції для ai і aj на k l повинні бути різними; це суперечить допущенню, що ai = aj. Теорема доведена.

Вхідну послідовність, що подається на M1| i, і М2| j, можна порівняти з двома шляхами, що починаються станами ai і aj на графі переходів для автоматів М1 і М2 відповідно. Теорема 5.10 означає, що якщо два початкових стани на цих шляхах еквівалентні, то кожні два відповідних стани на цих шляхах (тобто стани, у які переходять автомати з початкових станів після проходження того самого числа дуг) є також еквівалентними. Це положення ілюструється рис. 5.4, де показані шляхи є шляхами, що проходять М1 і М2, при додатку деякої вхідної послідовності до М1|ai і до М2|aj. Якщо ai і aj є еквівалентними, то k-і спадкоємці aik і ajk повинні бути еквівалентні для всіх k.

σ j1

M2

σ j

Рис.5.4. Шляхи в автоматах М1 і М2 при ai = aj

Наведені результати можуть бути використані в багатьох випадках для встановлення еквівалентності станів, коли еквівалентність інших станів уже встановлена. Нехай, наприклад, відомо, що пари станів {1,5} і {3,7} автомата M3, зображеного на рис. 5.3, є еквівалентними. Тоді пара {4,8} повинна бути також парою еквівалентних станів унаслідок того, що стани 4 і 8 є l-еквівалентними, а їх першими спадкоємцями є пари {1,5} і {3,7}. Якщо відомо, що стани в парах {4,8} еквівалентні, то стани в парах {1,5}, {2,6} і {3,7} повинні бути також еквівалентними, оскільки вони утворять пари відповідних станів на шляхах, що починаються станами 4 і 8.

95.K-еквів лентні розбиття

Далі нам знадобитися розбиття станів автомата на класи за такими правилами:

(1)усі стани, що належать до одного класу, повинні бути k-еквівалентними;

(2)усі стани, що належать до різних класів, повинні бути k-розрізненими.

Таке розбиття називається k-еквівалентним розбиттям автомата і позначається Pk. Класи Рk називаються класами k-еквівалентності і позначаються k1, k2, k3 і т.д. Стани, що належать до того самого класу, називаються суміжними станами; стани, що належать до різних класів, називаються розрізненими станами.

Рис. 5.5 і таблиця 5.2 представляють автомат А4. Для цього автомата 2-еквівалентне розбиття має вигляд

Р2: 21 = {1, 3, 5, 7, 8}, 22 = {2, 4, 6}, 23 = {9}.

Легко перевірити за допомогою графа переходів автомата M4, що суміжні стани в Р2 є 2- еквівалентними, а розрізнені стани є 2-розрізненими. Жодний стан автомата M4 не є 2-еквівалентним стану 9 (за винятком самого стану 9), і, отже, стан 9 утворить клас, що складається з одного стану, - одноелементний клас.

(β/1)

(γ/1)

Рис. 5.5. Автомат M4.

106

Жодний стан не може належати одночасно двом різним k-еквівалентним класам, тому що тоді цей стан був би k-розрізненим стосовно самого себе. Звідси робимо висновок, що загальне число станів у Рk дорівнює загальному числу станів в автоматі.

Автомат M4 Таблиця 5.2

Лема 3.5. k-еквівалентне розбиття автомата єдине.

Доведення. Припустимо, що розбиття Рk, яке складається з k1, k2… ku, не є єдиним. Тоді для цього ж автомата повинне бути інше k-еквівалентне розбиття, скажемо Р k, що складається з k1, k2… kv... Нехайkr = {ar1,ar2,…,ard}... Оскільки стани з kr є k-еквівалентними й оскільки не має жодного стану поза kr, що є еквівалентним якому-небудь стану з kr, то в Рk повинен бути клас станів, скажемо k1, що складається зі станів ar1, ar2 , …, ard і що не містить ніяких інших станів. Припустивши, що r приймає значення 1,2, ..., u, одержимо, що кожному класу в Pk відповідає ідентичний клас у Р k. Оскільки загальне число станів у Р k повинно бути таким же, як у Рk, то Рk і Р k повинні бути однаковими і, отже, Рk є єдиним. Лема доведена.

Лема 5.6. Стани, що є розрізненими в Рk, повинні бути розрізненими в Рk+1.

Доведення. Відповідно до леми 5.4 два стани, що є k-розрізненими, є і (k+1)-розрізненими. Тоді справедливість доказуваної леми безпосередньо випливає з визначення Рk і Рk+1. Лема доведена.

Наприклад, Р3 автомата M4 не може містити такі класи, як {1,3,6} і {2,5,9}, оскільки ці класи, містять стани, що у Р2 є розрізненими.

Лема 5.7. Якщо автомат М має два розрізнені, але k-еквівалентні стани, то він також повинен мати два стани, що є, k-еквівалентними, але (k+1)-розрізненими.

Доведення. Нехай ai і aj будуть розрізненими k-еквівалентними станами автомата М і нехай вхідна послідовність h1, h2,…, hl буде найкоротшою вхідною послідовністю, що розрізняє стани ai і aj. Це означає, що ai і aj виробляють різні вихідні символи не раніш, ніж буде прикладений вхідний символ hl. Оскільки ai і aj є k-еквівалентними, то повинно бути l > k. Нехай (l – k – 1)-ми спадкоємцями ai і aj стосовно вхідної

послідовності h1, h2, …, h(l-k-1) будуть a i і a j відповідно; тому що l > k, то l–k–1 0, і ці спадкоємці завжди

існують. Тоді a i і a j можуть бути розрізненими при вхідній послідовності h(1-k), h(l-k+1),…, hl, довжина якої дорівнює l – (l–k–1) = k+1, Ці два стани не можуть бути розрізненими за допомогою ніякий іншої більш

короткої послідовності, тому що це суперечило б умові, що ai і aj є k-еквівалентними. Отже, a i і a j, є k- еквівалентними, але (k+1)-розрізненими. Лема доведена. Розглянута ситуація ілюструється рисунком 5.6.

Рис. 5.6. Ілюстрація до леми 5.7.

Припустимо тепер, що суміжні стани в кожнім класі еквівалентності розбиття Рk є еквівалентними. Тоді ясно, що Рk+u збігається з Рk для всіх невід‘ємних цілих u. Якщо два суміжних стани в Рk є розрізненими, то вони становлять собою два розрізнених стани, що є k-еквівалентними. У цьому випадку, відповідно до леми 5.7, автомат повинний мати два стани, що є k-еквівалентними, але (k+1)-розрізненими. Отже, Рk повинно містити два суміжних стани, що стають розрізненими в Рk+1. Таким чином, якщо суміжні стани в якому-небудь класі з Рk є розрізненими, то розбиття Рk+1 повинне відрізнятися від розбиття Рk. Якщо Рk+1 відрізняється від Рk, то, відповідно до леми 5.6, повинен існувати «власний поділ» Рk, що повинне

107

виходити розщепленням одного чи декількох класів Рk на два чи більше підкласи. Тепер можна стверджувати, що справедлива наступна

Теорема 5.11. Рk+1 повинна бути власним поділом Рk, якщо не у всіх класах Рk суміжні стани є еквівалентними. У противному випадку Рk і Рk+1 збігаються.

Для автомата M4, наприклад, маємо:

Р3: 31 = {1,3,5,7,8}, 32 = {2,4}, 33 = {6}, 34 = {9}, що є власним поділом Р2, і

Р4: 41 = {1,3,8}, 42 = {2,4}, 43 = {5,7}, 44 = {6}, 45 = {9}, що є власним поділом Р3.

Однак видно, що

Р5: 51 = {1, 3, 8}, 52 = {2, 4}, 53 = {5, 7}, 54 = {6}, 55 = {9} збігається з P4 і, отже, суміжні стани в кожнім класі P4, є еквівалентними.

96.М тричний метод визн чення еквів лентного розбиття втом тів

Існує кілька методів визначення еквівалентного розбиття автомата, з яких ми виберемо матричний метод, що оперує над матрицею переходів. Хоча метод матричного розбиття не має переваг у порівнянні з іншими методами, він дає нову і корисну інтерпретацію поняття класів еквівалентності.

Визначення. Симетричною перестановкою відносно матриці називається перестановка рядків і стовпців матриці за одним і тимо ж правилом. Отже, якщо позначення, що присвоєні рядкам і стовпцям матриці [М], симетричні щодо головної діагоналі, то ці позначення будуть симетричними в будь-якій симетричній перестановці цієї матриці. Симетричне розбиття [М] становить поділ груп рядків і стовпців пунктирними лініями таким чином, що якщо є пунктирна лінія, що розділяє рядки ai і aj то є також пунктирна лінія, що розділяє стовпці ai і aj і навпаки.

Матриця [М](k) для автомата М є матрицею [М], у якій симетрична перестановка і симетричне розбиття мають наступні властивості: рядки (і стовпці), що відповідають суміжним станам Рk, згруповані разом, а кожна група відділена від сусідніх груп пунктирними лініями; порядок груп у матриці і порядок рядків (стовпців) у кожній групі довільні; якщо Рk містить rk класів, то симетричне розбиття утворить rk рядків підматриць з rk підматрицями в кожному рядку.

2.1. Побудова матриці М(1). Згрупуємо рядки матриці [М] так, щоб два рядки належали до однієї і тєї ж групи тоді і тільки тоді, коли вони утворють однакові множини пар вхід-вихід. Кожна така група являє собою клас 1-еквівалентності. Роблячи симетричну перестановку і симетричне розбиття [М] відповідно до правил, описаними вище, одержимо [M](1). Прикладом матриці переходів є матриця (5.15) автомата M4 (рисунок 5.5). Рядки 1, 3, 5, 7 і 8 у [M4] представляють пари вхід-вихід (α/1), (β/0) і (γ/0). Рядки 2, 4, 6 і 9 представляють пари вхід-вихід (α/0), (β/1) і (γ/1). Тоді матриця [M4](1) будується угрупуванням рядків (і стовпців) 1, 3, 5, 7 і 8 і рядків (і стовпців) 2, 4, 6 і 9, при цьому групи розділяються пунктирною лінією. Матрицею [M4](1), отриманої в результаті цих операцій, є матриця (5.16).

2.2. Побудова матриці. [M](k+1) на основі [М](k) (k 1). Нехай ai, і aj – два рядки в одній і тій же групі рядків [M](k). Якщо в кожній з підматриць, розташованих на перетині рядків ai і aj, рядки ai і aj мають однакові множини пар вхід-вихід, то ai і aj становлять собою k-еквівалентні стани, перші спадкоємці яких

стосовно будь-якого вхідного символу є k-еквівалентними, тому стани ai і aj є (k+1)-еквівалентними. Якщо ці умови не мають місця, то ai і aj є (k+1)-розрізненими. Таким чином, матриця [M](k+1) може бути побудована

по [M](k), якщо розділити кожну групу рядків у [M](k) на підгрупи так, щоб два рядки належали до однієї і тієї ж підгрупи тоді і тільки тоді, коли вони мають однакові пари вхід-вихід у кожній з перетинаємих ними

підматриць rk. Кожна така група являє собою (k+1)-еквівалентний клас. Зробивши симетричну перестановку і симетричне розбиття матриці [M](k), одержимо [M](k+1). Наприклад, рядки 1, 3, 5, 7 і 8 у [M](1) мають

однакові множини пар вхід-вихід в кожній підматриці, яку вони перетинають. З іншого боку, рядки 2, 4 і 6 утворюють у цих підматрицях множини пар вхід-вихід, що відрізняються від множин пар вхід-вихід, утворених рядком 9. Отже, рядки 2, 4 і 6 і рядок 9 дають дві різні групи в [M7](2), як показано в (5.17).

Матриця [M](k) дає еквівалентне розбиття тоді, коли ніяке подальше розбиття не може бути зроблене (тобто коли кожна підматриця має один рядок і один стовпець чи коли рядки всередині кожної підматриці мають однакові множини пар вхід-вихід). При цих умовах різні групи рядків (чи стовпців) є класами k- еквівалентності, де k може бути зроблене як завгодно великим; тому ці групи являють собою класи еквівалентності автомата М. Відповідно до теореми 5.12, це може мати місце для деякого значення k n-1 [M7] =

108

(5.16)

Матриці (5.15) – (5.19) ілюструють описуваний метод еквівалентного розбиття автомата M7. Матриця [М](4) подальше розбиття якої неможливо, очевидно, містить еквівалентне розбиття {1,3,8}, {2,4},

{5,7}, {6} і {9}, що співпадає з приведеним вище розбиттям.

[M7](2) =

109

Визначення. Нехай М – скінчений автомат з n еквівалентними класами, позначеними 1, 2, …, n, і нехай (l) становить собою який-небудь стан у l. Мінімальна форма автомата М, яку будемо позначати через Mmin, становить собою автомат з n станами, що утворюють множину { 1, 2, .., n}.

Мінімальний автомат будується на основі автомата М наступним чином. Позначимо характеристичні функції автомата М через fz і fs, а автомата Mmin через fz min і fs min. Тоді, якщо

Зазначимо, що якщо при поданні i на М в визначеному стані з множини u виробляється вихідний символ j, то при поданні i в будь-якому стані з u також виробляється вихідний символ j. Аналогічно, якщо при поданні i, на М в деякому стані з множини u M переходить у стан, що належить v, то при поданні i в будь-якому стані з u М переходить у стан, що належить v. Таким чином, при побудові Mmin за умовою (5.20) не виникає ніякої невизначеності внаслідок того, що (u) є довільним станом, що належить класу u, і що (v) є довільним станом, що належить класу v.

Процес відшукання мінімальної форми автомата називається мінімізацією автомата. Мінімізація автомата М полягає у визначенні еквівалентного розбиття М і в наступному застосуванні (5.20) для побудови Mmin. Оскільки при застосуванні (5.20) для усіх станів автомата М, що належать тому самому класу еквівалентності, визначений однаковий результат, то індивідуальне розпізнавання кожного стану стає непотрібним. Для цілей мінімізації важливе розпізнавання класу, до якого належить кожен стан. Тому всім станам М, що належать класу еквівалентності l, можна приписати загальне позначення, наприклад, l. Після цього (5.20) може бути інтерпретоване як формулювання того, що автомат Mmin отримується з автомата М шляхом «об'єднання» однаково позначених станів в один стан. Способи, якими це об'єднання здійснюється, істотно залежать від того, яким чином визначений автомат – таблицею, графом чи матрицею. Хоча розуміння цих способів полегшується завдяки попередній інтуїтивній інтерпретації умови (5.20), їхня справедливість не залежить від цієї інтерпретації і випливає безпосередньо із самої умови.

Побудов т блиці переходів втом т Mmin. Якщо задани таблиця переходів і еквівалентне розбиття 1, 2, …, n автомата М, то таблиця переходів автомата Mmin може бути побудована таким чином:

(1)замінимо позначення кожного стану, що маємо в таблиці переходів М, на позначення класу, якому даний стан належить;

(2)з кожної групи рядків з однаковими позначеннями в клітинках основного стовпця (усі такі рядки

єоднаковими в обох підтаблицях zv, і sv+1) викреслимо всі рядки, крім одного.

Отримана таблиця є таблицею переходів Mmin.

Наприклад, автомат M7, представлений таблицею 5.2, має класи еквівалентності {1,3,8}, {2,4}, {5,7}, {6} і (9). Позначимо їх довільно, наприклад 1, 2, 3, 4 і 5 відповідно. Виконуюячи перший крок процедури, замінимо кожне позначення «1», «З», і «8» в основному стовпці й у sv+1 підтаблиці таблиці 5.2 на

«1», кожне «2» і «4» – на «2», «5» і «7» – на «3», «6» – на «4», «9» – на «5». Отримана в результаті таблиця переходів наведена в таблиці 5.15. Викреслювання всіх рядків, які повторюються, дає таблицю переходів M7min, наведену в таблиці 5.16.

Таблиця 5.15

Результат виконання кроку 1 при побудові таблиці переходів для автомата M7min

110