Я читал, что каждый недетерминированный конечный автомат (NFA) может быть перенесен в детерминированный конечный автомат (DFA). Это можно сделать для регулярного выражения kleene star, скажем, *? 
Детерминированный конечный автомат звезды Клейна
Выше NFA для *.
Да. Конечный автомат звезды Клейн имеет два состояния. Начальное состояние является окончательным и имеет переход к самому себе для a и переход в другое состояние для всех остальных символов. Другое государство имеет переход к себе для каждого символа.
Таким образом, он принимает пустую строку (поскольку исходное состояние является окончательным) и произвольное количество повторений a. Все, что не является a, отправит DFA в другое состояние, которое не является окончательным, и от которого нет выхода.
Это немного сложнее, если вы примените звезду Kleene к регулярному выражению, более сложному, чем один символ, но это всегда можно сделать: просто вставьте NFA для регулярного выражения в красную часть изображения, которое вы показали , и применить стандартный алгоритм Powerset construction для преобразования NFA в DFA. Я настоятельно рекомендую изучить этот алгоритм; если вы поймете, почему он работает, вы увидите , почему каждый NFA может быть преобразован в DFA.
Это только одно начальное состояние, которое также является принимающим. У него есть цикл self, который принимает «a». 