2015-07-14
1527
Два автомати, у яких збігаються як вхідні, так і вихідні алфавіти, називають еквівалентними, якщо для будь-якого вхідного слова їх вихідні слова збігаються за умови, що обидва автомати мали один і той же початковийстан.
Для будь-якого автомата Мура можна створити еквівалентний йому автомат Мілі та навпаки. Описуючи алгоритми взаємної трансформації даних автоматів, будемо нехтувати вихідним сигналом, який пов'язаний із початковим внутрішнім станом в обох автоматах.
Визначення Два стани qs і q m є еквівалентними, якщо d(qs, X) = d(qm, X), де d - функція переходу, X - вхідне слово довільної довжини.
Іншими словами, стани еквівалентні, якщо у відповідь на одні і ті ж вхідні слова виробляється одна і та ж послідовність станів, незалежно від того в якому з двох станів qs або qm знаходився автомат в початковий момент часу. Якщо два стани еквівалентні, то один стан можна замінити на інший.
Окрім еквівалентних станів існує поняття k - еквівалентних станів: 1-еквівалентні, 2-еквівалентні і так далі
|
|
|
Визначення Два стани qs і q m є k-еквівалентними, якщо d(qs, Xk) = d(qm, Xk), де d - функція переходу, Xk - вхідне слово довільної довжини k
Розглянемо спочатку послідовність дій у разі перетворення автомата Мура на еквівалентний йому автомат Мілі.
Два КА вважаються еквівалентними, якщо:
1. Обидва КА визначені на одній і тій же множині допустимих вхідних послідовностей символів (вхідних слів).
2. Вхідні алфавіти обох КА не містять в собі тотожних символів і можуть бути взаємно і однозначно відображені один в одного. Аналогічна умова виконується і для вихідних алфавітів.
3. При подачі на входи КА однакових вхідних слів (з числа допустимих) на виходах з'являються також однакові вихідні слова.
4. Допускається затримка вихідних послідовностей КА на деяке довільне, але кінцеве число тактів. Якщо довжина вхідної можливої послідовності необмежена, еквівалентність КА вважається повною. Якщо довжина послідовності обмежена k символами, автомати називаються k-еквівалентними.
