Существует бесконечно много таких графов переходов. Один из способов думать об этом заключается в том, что вы можете легко построить семейство бесконечно многих графов переходов следующим образом. Предположим, что я хочу принять язык a n для некоторого фиксированного n (то есть n копий буквы a). Тогда я мог бы построить граф перехода, который принимает этот язык следующим образом. Начните с начального состояния, затем соедините n новых состояний в конец этого состояния, каждое с переходом «а» в следующее состояние. Сделать последнее состояние принятия.
Чтобы увидеть, что их насчитывается только бесконечно много, мы можем подумать, как бы мы описали эти автоматы. Мы могли бы сделать это, записав число состояний в унарном виде, затем переходы между этими состояниями в виде списка кортежей (начало, конец, символ) (все они закодированы в двоичном виде), затем принимающие состояния в виде списка чисел состояния в одинарных. Объединенные вместе, это двоичная строка, и имеется только много конечных двоичных строк.