Асинхронні автомати, що тактуються
Визначення. Асинхронні автомати, що тактуються, задовольняють умові:
a) вхідний алфавіт Х автомата А розбивається на дві підмножини
X’={х'1, х'2,…x’m} і X’’={х'’1, х'’2,…x’’e};
b) при подачі на А якої-небудь букви х'j Î Х’ існує не менш одного переходу автомата А в будь-якій стан;
c) будь-яка буква х''j Î Х’’ не викликає жодного переходу автомата А в новий стан і на виході з'являється порожній сигнал ”e”;
d) забороняється подача на вхід автомата А послідовностей, будь-які дві поруч розташовані букви яких є літерами підмножини Х’.
Приклад. Вхідна послідовність вигляду <х'1 х'’2 х'2 х'’1 х'’3 х'3 х'’2 х'1>.
Приклад. Автомат керування ліфтом, що обслуговує три поверхи. Натискання двох і більш кнопок неприпустимо.
d:S´X®S, l:S´X®Y
Таблиця 19.2
S X | s1 | s2 | s3 |
x1 | s1/ - | s1/y2 | s1/y2 |
x2 | s2/y1 | s2 / - | s2/y2 |
x3 | s3/y1 | s3/y1 | s3/ - |
Тут y1- рух нагору, y2 - рух униз. Усі стани автомата стійкі, але вихідні сигнали – не стійкі, отже, автомат асинхронний.
Перетворення автоматів Мілі і Мура
Для будь-якого автомата Мура можна побудувати еквівалентний йому автомат Мілі і навпаки.