x2)..і так далі. На виході отримаємо рядок y1, y2…yn, який однозначно визначається початковим станом і вхідним рядком х1, х2, х3….хn. Цю залежність позначаємо yi, yn = ga(x1,….,xn). Кажемо, що ga відображення визначене автоматом. Якщо для однакових вхідних рядків х1, х2, х3….хn вихідні рядки двох автоматів завжди збігаються (якщо починати відповідно зі станів a i a’) то стани a i a’ називаються еквівалентними. Еквівалентність означає що автомат А в стані а, і автомат А’ в стані а’ поводять себе однаково, з точки зору вихідних рядків. Еквівалентність позначається a~a’.
Два автомати називаються еквівалентними, якщо кожному стану будь-якого з них, існує еквівалентний стан іншого автомата. Таким чином, автомати є еквівалентними, якщо їх не можна відрізнити, спостерігаючи за вхідними і вихідними рядками.
Припустимо, що дано два автомати (A, X, Y, f, g) і (A2, X, Y, f2, g2). З однаковими вхідними і вихідними алфавітами. Відображення U з множини А в множину А2 називають гомоморфізмом з першого автомата в другий, якщо для кожного а є А, х є Х виконуються рівності.
g2 (U(a), x) = g(a, x)
f2 (U(a), x) = U(f1(a, x))
Перша рівність означає що коли автомат А перебуває у довільному стані а, а автомат А2 у відповідному йому стані стані а2 = U(a) і на вхід обох автоматів надходить той самий символ х є Х, то вихідні символи y1(a, x), g2(a2, x) = g2(U(a), x) теж будуть однаковими. Друга рівність означає що нові стани цих автоматів теж будуть відповідними.
Теорема:
Якщо U – гомоморфізм автомата (A, X, Y, f, y) в автомат (A2, X, Y, f2, g2), і а0 є А – довільний стан, то стани а0 є А, і U(a0) – еквівалентні.
Бінарне відношення “~” на множині А станів довільного автомата (A, X, Y, f, y) називається конгруентністю, якщо для кожних станів а1 ~ a2 виконуються рівності.
g(a1, X) = g(a2, x)
f(a1, X) ~ f(a2, x).
Не важко довести що однорідні стани є еквівалентними з точки зору вихідних рядків, тобто при однакових вхідних рядках х1, х2, х3….хn вихідні рядки y1, y2, y3….yn та y’1, y’2, y’3….y’n . отримані в цих станах знову однакові. Для кожної конгруентності на автоматі (A, X, Y, f, y) можна утворити так званий фактор автомат (A’, X, Y, f’, y’), в якому А’= А/~. Множина класів еквівалентності. В кожен клас об’єднаємо всі стани конгруентні між собою. Тоді множина станів А розглядається на непорожні перетинні класи. Кожен такий клас вважаємо новми станом нового автомата А’. Клас стану а позначаємо [а]. Якщо [a] = [b], то а і в – конгруентні. Тоді за означенням g(a,x) = g(b,x) для всіх х є Х. Тому можемо покласти g’([a], x)= g(a, x).
Теорема.
Якщо для автоматів (А, Х, У, f, g), (A2, X, Y, f2, g2) існує гомоморфізм U: A -> A2, для якого U(A)=A2, тоюто кожен стан другого автомата відповідає деякому стану першого, то ці автомати еквівалентні.
Для кожного автомата Мілі існує відповідний автомат Мура.