justify"> б) ( s A? SA) ( s B? SB) ("x? X) l A? B ((s A, s B), x)=(l A (s A, x), l B (s B, x)).
Теорема Мура
Два кінцевих автомата з однаковим вхідним алфавітом X є еквівалентними тоді і тільки тоді, коли для будь-якого досяжного стану (s A, s B) в їх прямому творі (рис.4) А? У справедливо [2]:
("x? X) l A (s A, x)=l B (s B, x).
Пряме твір кінцевих автоматів А і В, зображених на рис. 4, представлено на рис. 4А. На рис. 4В показаний цей же автомат з викинутими недосяжними станами.
Малюнок 4 - Кінцеві автомати
Малюнок 5 - Пряме твір кінцевих автоматів
За графу переходів (рис.5) видно, що з усіх досяжних станів під впливом вхідних сигналів автомат А? У видає пари однакових вихідних сигналів.
Отже, автомати А і В еквівалентні.
1.3 Мінімізація кінцевого автомата
Різні кінцеві автомати можуть функціонувати однаково, навіть якщо у них різне число станів. Важливим завданням є знаходження мінімального кінцевого автомата, який реалізує заданий автоматне відображення [3].
Еквівалентними природно назвати два стани автомата, які не можна розрізнити ніякими вхідними словами.
Визначення 1: Два стану р і q кінцевого автомата
А=(S, X, Y, s 0, d, l) називаються еквівалентними (позначається p ~ q), якщо ("a? X *) l * (p, a)=l * (q, a).
Еквівалентні стану можна об'єднати в один клас і побудувати новий автомат, станами якого є класи еквівалентних станів. Якщо ми можемо визначити на безлічі станів КА «максимально можливе» розбиття на класи еквівалентності, то, вибираючи його класи еквівалентності як нові стани, отримаємо мінімальний автомат, еквівалентний вихідному.
Алгоритм мінімізації КА
Алгоритм мінімізації кінцевого автомата [3] [4] полягає в послідовній побудові на безлічі станів автомата А разбиений p 0, p 1, ..., p? , Таких, що в один клас розбиття pk потрапляють k-еквівалентні стану, тобто ті, які невиразні вхідними словами довжиною? k. Такі стани будемо вважати що знаходяться в відношенні еквівалентності ~ k. Якщо p і q не є k-еквівалентними, то р і q назвемо k-помітними. З визначення 1 випливає, що
р ~ kq? ("A? X *, | a |? K) l * (p, a)=l * (q, a).
Очевидно, що в будь-якому автоматі всі стани 0-еквівалентні, оскільки при подачі порожнього слова e на вхід автомата виходом є також порожнє слово e незалежно від стану, в якому автомат знаходиться.
Наступне розбиття p 1 також легко побудувати. Дійсно, за визначенням в один блок p 1 потрапляють всі стани, в яких автомат однаково реагує на вхідні сигнали: р ~ 1 q? ("X? X) l (p, x)=l (q, x). Разбиття p 0, що містить один єдиний блок, в який входять всі стану автомата, і p 1, в кожному блоці якого зібрані статків, не помітні вхідними сигналами, є вихідними при побудові ланцюжка разбиений p 0, p 1, ..., p?.
Якщо ми зможемо визначити, як будувати наступне розбиття з попереднього, то починаючи з p 1 ми зможемо послідовно побудувати і весь ланцюжок.
Теорема 2. Нехай р ~ kq, k gt; 1. Для того щоб p ~ k + 1 q, необхідно і достатньо, щоб ("x? X) d (p, x) ~ kd (q, x).
Дійсно, для того щоб вхідне слово довжини k + 1, наприклад, слово x 0 x 1 x 2 ... xk, що не розрізняла пару станів р і q, потрібно всього лише, щоб автомат з цих станів переходив під впливом х0 в такі стани, які не помітні словом x 1 x 2 ... xk, т. е. щоб d (p, x 0) і d (q, x 0) були б k-невиразні (див. малюнок).
Очевидно, що якщо р і q (k + 1) -еквівалентни, то вони k-еквівалентні. Іншими словами, блоки розбиття p k + 1 є подблоков розбиття pk.
Оскільки число станів звичайно, може бути тільки кінцеве число послідовно зменшуються разбиений pk, починаючи з «найбільшого» розбиття p 0, що містить один єдиний блок.
Більше того, очевидно, що їх не більше, ніж число станів кінцевого автомата.
Однак послідовне побудова зменшуються разбиений, можна не продовжувати далі, як тільки два послідовних розбиття збігаються, оскільки справедлива теорема:
Теорема 3. Нехай p k + 1=pk. Тоді i gt; k? p i=p k. Зокрема, p k=p?.
З цієї теореми випливає, що як тільки ми отримаємо збіг p k + 1=pk, то алгоритм припиняє свою роботу і розбиття p? =Pk буде максимальним розбиттям множини станів кінцевого автомата на класи еквівалентних станів, за яким і визначається мінімальний кінцевий автомат, еквівалентний даном...
