Определение 2:асинхронный автомат (источник) — называется такой конечный автомат (источник) у которого все состояния (вершины) устойчивы по каждому входному знаку.

Физический смысл: если есть конечный автомат и есть входной канал A, то такты работы автомата определяются сменой входных знаков.

Математическое определение: для всех знаков и всех знаков из входного алфавита должно вы¬полнятся .
Такое же определение действует для источника , где автомат общего вида — синхронный.
определение 13:Достижимая вершина. Для входного знака из состояния вершина называется достижимой , если существует путь в графе. Помеченный входными знаками . Различают синхрон¬ную и асинхронную достижимость. При синхронной достижимости в этом пути существует единст¬венный знак . При асинхронной достижимости — число знаков произвольное(>=1) т.е. помечаю¬щий путь представлен так: .
определение 14: множество достижимых вершин( )- то множество вершин , которое достижимо из состояния при входном знаке .
Пример: рассмотрим выражение (регулярное)
Очевидно, не каждый язык является асинхронным. Для того чтобы представить любой язык асин¬хронным , необходимо чтобы регулярное выражение имело вид . в таком случае мы можем, упро¬стив . Из него видно, что после преобразования мы получили асинхронный язык.
Изобразим этот источник

Это асинхронный источник, так как все вершины устойчивы к каждому входному знаку. Проверим достижимость.
— это синхронная достижимость
— это асинхронная достижимость
Утверждение: Для любого недетерминированного источника с n вершинами существует эквивалент¬ный ему детерминированный источник, имеющий не более чем 2n состояний
Доказательство: А) Пусть задан источник , где — набор входных знаков; -множество вершин; -множество дуг — это отображение, которое задает дуги этого графа.
Построим неотличимый от него источник .Очевидно , где — детерминированный источник.
В)
шаг1:
для множества начальных вершин (состояний) и всех знаков строим систему подмножеств вершин достижимых из вершин множества для всех входных знаков. Используем синхронную или асин¬хронную достижимость. Объявляем полученную систему множеств множеством вершин источ¬ника .

шаг к:
пусть получено множество вершин источник .
шаг к+1:
для каждой полученной ранее вершины источника -(а это множество вершин исходного источника)
Строим множество вершин источника , которые достижимы из вершин (полученных на предыду¬щем шаге) для всех знаков. Считаем полученные множества новыми вершинами источника т.е. новое множество вершин будет
шаг s:
завершаем построение, если разбиение на множество вершин не изменилось.
С) Докажем, что полученное множество вершин является вершинами детерминиро¬ванного источника, неотличимого от исходного. Может быть построено не более чем 2n вершин, где — число вершин исходного источника
Пример: пусть задан источник или же автомат в контексте распознавания входных знаков

1. строим таблицу
A\Q X Y
{0} {1,2} {0}
{1,2} {0,2,3} {1,2,3}
{0,2,3} {1,2,3} {0,3}
{1,2,3} {0,1,2,3} {1,2,3}
{0,3} {1,2,3} {0,3}
{0,1,2,3} {0,1,2,3} {0,1,2,3}

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

QD {0} {1,2} {0,2,3} {1,2,3} {0,3} {0,1,2,3}
QD` 1 2 3 4 5 6

заключительными являются те вершины, которые содержат хотя бы одну заключительную вершину исходного источника (в данном случае 1).
Проверка