Минимальная длина прокачки для обычного языка

Оно будет меньше или равно количеству состояний в минимальном DFA для языка минус один. Поэтому преобразуйте регулярное выражение в DFA, сверните его и подсчитайте состояния. Для вашего примера:

0001*

SOURCE    SYMBOL    DESTINATION
q1        0         q2
q1        1         q5
q2        0         q3
q2        1         q5
q3        0         q4
q3        1         q5
q4        0         q5
q4        1         q4
q5        0         q5
q5        1         q5

Почему он равен этому? Потому что это максимальное количество переходов, которые вы можете совершить в DFA, не посещая некоторое состояние дважды. Как только вы посещаете состояние дважды, вы зацикливаетесь.

Конечно, в минимальном DFA языка может отсутствовать путь такой длины. В этом случае вы можете найти самый длинный путь (из начального состояния), который не посещает состояние дважды, используя что-то вроде поиска в глубину графа автомата и наблюдая, насколько длинный путь вы можете проследить. Это был бы твой настоящий ответ.