Асинхронні автомати, що тактуються

Визначення. Асинхронні автомати, що тактуються, задовольняють умові:

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 - рух униз. Усі стани автомата стійкі, але вихідні сигнали – не стійкі, отже, автомат асинхронний.

Перетворення автоматів Мілі і Мура

Для будь-якого автомата Мура можна побудувати еквівалентний йому автомат Мілі і навпаки.