Мінімізація числа станів автоматів Мілі і Мура

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

Розглянемо алгоритм мінімізації числа станів цілком визначеного автомата Мілі, запропонованого Ауфен - Кампом і Хоном. Основна ідея цього методу полягає в розбитті всіх станів вихідного абстрактного автомата на попарно не пересікаючі класи еквівалентних станів і в заміні кожного класу еквівалентності одним станом. Таким чином, виходить щорезультаті мінімальний автомат має стільки ж станів, на скільки класів еквівалентності розбиваються стани вихідного автомата.

Два стани автомата z_i і z_j називаються еквівалентними, якщо l(z_i, x) = l(z_i, x) для усіляких вхідних слів х. Якщо z_i и zj не еквівалентні, то вони різні. Стану z_iі z_j к- еквівалентні, якщо l (z_i, x_k) = l (z_i, x_k) для усіляких вхідних слів хк довжини k. Відповідні розбивання на класи еквівалентних і k-еквівалентних станів будемо позначати через p і p_к. Якщо, наприклад, z_i і z_j, еквівалентні, то з погляду реалізацій автомата на усілякі вхідні слова не має значення, знаходиться автомат у стані z_i або z_jі одне з них може бути вилучене з множини z. Якщо кожен клас еквівалентності містить тільки одиь стан, множина Z нескоротна. Якщо ж один чи кілька класів містять більше одного елемента, всі елементи, крім одного в кожному класі, можуть бути виключені з множині Z, у результаті чого виходить автомат з мінімальним числом станів.

Роботу алгоритму цроілюструємо на прикладі абстрактного немінімального автомата Мілі, заданого табл.4.9 і 4.10.

Таблиця 4.9

Вхідний сигнал	Стан
z1	z2	z3	z4	z5	z6	z7	z8
x1	z1	z3	z4	z2	z7	z8	z3	z1
x2	z2	z8	z3	z5	z4	z7	z8	z6

Таблиця 4.10

Вхідний сигнал	Стан
z1	z2	z3	z4	z5	z6	z7	z8
x1	y1	y1	y1	y2	y1	y1	y1	y1
x2	y1	y2	y1	y1	y1	y2	y2	y1

1. Будуються непересічні класи 1-еквівалентності: а₁, b₁, с₁,d₁,...

До одного класу 1-еквівалентності відносяться стани, для яких збігаються значення вихідних сигналів у таблиці виходів (табл.4.10). Для розглянутого приклада одержимо:

Ці класи визначають по таблиці переходів (табл.4.9) і таблиці виходів (табл.4.10) автомата Мілі.

2. Проводиться новий поділ станів на класи. Для цього виробляється заміна кожного зі станів Z_i+1 в табл. 4.9 позначенням класу 1-еквівалентності, в який входить цей стан

Поєднуємо кожному класі стани відзначені однаковою послідовністю букв і одержуємо розбиття на класи 2-еквівалентності:

Аналогічно п.2 проводиться нове розбиття

Одержуємо розбиття на класи 3-еквівалентності:

4. Якщо деякі класи черговго розбиття (к+1- еквівалентності) цілком збігаються з класами попереднього розбття (k-еквівалентності), а інші класи містять тільки по одному стану то алгоритм закінчується.

При цьому стани в кожному класі одержуваного розбиття (к +1 -еквівалентності) еквівалентні. У розглянутому прикладі класи с_з і d₃ збігаються з b ₂ і с₂, а інші класи а₃, b₃, е₃, f₃ містять тільки по одному стану. Тому розбиття станів на класи еквівалентності на цьому закінчується.

У кожному класі одержаного розбиття залишають тільки по одному стану, відкинувши інші.

Позначивши

одержимо мінімальний автомат А' зі станами Z'₁, Z'₂, Z'₃, Z'₄, Z'₅, Z'₆, (табл. 4.11 і 4.12).

Таблиця 4.11

Вхідний сигнал	Стан
z1^’	z2^’	z3^’	z4^’	z5^’	z6^’
x1	z1^’	z1^’	z4^’	z6^’	z2^’	z3^’
x2	z4^’	z2^’	z3^’	z2^’	z4^’	z6^’

Таблиця 4.12

Вхідний сигнал	Стан
z1^’	z2^’	z3^’	z4^’	z5^’	z6^’
x1	y1	y1	y1	y1	y1	y2
x2	y1	y1	y1	y2	y2	y1

При мінімізації автоматів Мура вводиться поняття 0-еквівалентності станів і розбиття множини станів на 0-класи, Будь-які однаково відзначені вихідними сигналами стани; автоматів Мура називаються 0-еквівалентними. Якщо два 0-еквівалентних стани будь-яким вхідним сигналом переводяться в два 1-еквівалентних стани, то вони називаються 1-еквівалентними. Усі подальші класи еквівалентності станів для автоматів Мура визначаються аналогічно приведеному вище для автоматів Мілі. Алгоритм мінімізації числа внутрішніх станів автомата Мура проілюструємо на прикладі немінімального автомата, заданого табл. 4.13.

Таблиця 4.13

Вихідний сигнал

y1

y1

y3

y3

y3

y2

y3

y1

y2

y2

y2

y2

Стан

z1

z2

z3

z4

z5

z6

z7

z8

z9

z10

z11

z12

Вхідний сигнал

x1

z10

z12

z5

z7

z3

z7

z3

z1

z7

z1

z5

z2

x2

z5

z7

z6

z11

z9

z11

z6

z4

z6

z8

z9

z8

1. Визначаємо розбиття на класи 0-еквівалентних станів по табл.4.13, поєднуючи однаково відзначені вихідними сигналами стани

2. Визначаємо розбиття p₁на класи 1-еквівалентних станів. Для цього виробляється заміна кожного зі станів Z ₁₊₁в табл. 4.13 позначенням класу 1-еквівалентності, у який входить цей стан:

Об'єднаємо в кожному класі стани, відзначені однаковою послідовністю букв і одержуємо розбиття на класи 1- еквивалентності:

Процес розбиття завершений, оскільки класи чергового розбиття (2-еквівалентності) цілком збігаються з класами попереднього розбиття (1-еквівалентності). Розбиття p₁ є розбиття безлічі станів немінімального автомата Мура на класи еквівалентних між собою станів.

4. У кожному класі отриманго розбиття залишають тільки по одному станру виключивши інші. Позначивши

одержимо мінімальний автомат А' зі станами Z'₁,Z'₂,Z'₃,Z'₄ (табл. 4.14).

Таблиця 4.14

Вихдний сигнал	y1	y2	y2	y3
Стан	z1^’	z2^’	z3^’	z4^’
Вхідний сигнал	x1	z3^’	z4^’	z1^’	z4^’
x2	z4^’	z2^’	z1^’	z2^’

Задача мінімізації числа станів часткових (нецілком визначених) автоматів істотно складніше, ніж для цілком визначених автоматів. З алгоритмом мінімізації часткових автоматів можна ознайомитися в роботі [3].

Дата добавления: 2015-06-27