Синхронные и асинхронные цифровые автоматы

Состояние a_s автомата S называется устойчивым состоянием, если для любого входа z_fÎX, такого, что d(a_m, z_f) = a_s, имеет место d(a_s, z_f) = a_s. Это означает, что если автомат перешёл в некоторое состояние под действием z_f, то выйти из этого состояния он может только под действием другого, отличного от z_f сигнала.

Автомат S называется асинхронным, если каждое его состояние a_s ÎA - устойчиво. Автомат S называется синхронным, если он не является асинхронным.

Созданные для практических применений цифровые автоматы всегда являются асинхронными, а устойчивость их состояний всегда обеспечивается тем или иным способом, например, введением сигналов синхронизации.

Таким образом, оказывается, что техническая терминология противоречит математической терминологии, так как, согласно приведённым выше определениям, синхронизированные (технический приём) цифровые автоматы всегда являются асинхронными (математическое определение).

На уровне абстрактной теории, когда цифровой автомат - всего лишь математическая модель, не отражающая многих конкретных особенностей его возможной реализации, часто оказывается более удобным оперировать с синхронными цифровыми автоматами.

Пример асинхронного цифрового автомата Мура S₄ приведён в отмеченной таблице 22, а его граф - на рис.25. Очевидно, что все его состояния устойчивы. Если в таблице переходов асинхронного цифрового автомата некоторое состояние a_s стоит на пересечении строки z_f и столбца a_m (m ¹ s), то это же состояние a_s обязательно должно встретиться в этой же строке в столбце a_s. В графе асинхронного цифрового автомата, если в некоторое состояние a_s имеются переходы из других состояний под действием каких-то сигналов, то в вершине a_s должна быть петля, отмеченная символами тех же входных сигналов.

Ранее приведенные примеры описаний цифровых автоматов S₁, S₂ и S₃ таблицами и графами, являются примерами синхронных цифровых автоматов.

Связь между математическими моделями