в довільному з станів і під впливом вхідного сигналу х э X переходити в новий стан, який залежить від теперішнього стану А, і символу х, і позначається f(a, x). При цьому на вихід автомата подається вихідний символ h(0, x) є Y.
Якщо автомат має скінченні множини станів вхідних і вихідних символів, то його зручно зоображати графом, вершини якого – стани, а стрілки – переходи між ними. Є автомати, в яких з того ж стану під дією того ж вхідного символа автомат може перейти в кілька можливих станів, або видати кілька різних вихідних символів, тобто його поведінка не визначена однозначно. Такий автомат називається недетермінованим.
Можливий також випадок коли для деякого стану і деякого символу взагалі не визначено відповідного переходу. В цьому випадку вважаємо що автомат припиняє роботу. Такий автомат називається не цілком визначеним.
Важливим є клас автоматів, для яких вихідний символ однозначно визначається тим станом а = f(a, x), куди переходить автомат. Якщо ця залежність визначається функцією y = h(a), то функція виходів рівна y(a, x) = h(f(a,x)). Функція h називається функцією позначок. Вважаємо що в кожній вершині а є позначка h(a’), яка подається на вихід, коли автомат переходить у стан а’. Такий автомат називається автоматом Мура. Не кожен автомат Мілі є автоматом Мура.
Цей автомат не є автоматом Мура, оскільки повинен однозначно визначатись вихід залежно від х чи y. Переходячи в стан х можна отримати на виході і a i b.
Два автомати називаються еквівалентними, якщо кожному стану будь-якого з них, існує еквівалентний стан іншого автомата. Таким чином, автомати є еквівалентними, якщо їх не можна відрізнити, спостерігаючи за вхідними і вихідними рядками.
Припустимо, що дано два автомати (A, X, Y, f, g) і (A2, X, Y, f2, g2). З однаковими вхідними і вихідними алфавітами. Відображення U з множини А в множину А2 називають гомоморфізмом з першого автомата в другий, якщо для кожного а є А, х є Х виконуються рівності.
g2 (U(a), x) = g(a, x) 2.f2 (U(a), x) = U(f1(a, x))
Бінарне відношення “~” на множині А станів довільного автомата (A, X, Y, f, y) називається конгруентністю, якщо для кожних станів а1 ~ a2 виконуються рівності.1.g(a1, X) = g(a2, x) 2.f(a1, X) ~ f(a2, x).
Теорема.
Якщо для автоматів (А, Х, У, f, g), (A2, X, Y, f2, g2) існує гомоморфізм U: A -> A2, для якого U(A)=A2, тоюто кожен стан другого автомата відповідає деякому стану першого, то ці автомати еквівалентні.
Для кожного автомата Мілі існує відповідний автомат Мура.