Возьмите любой DFA для вашего языка. Он должен содержать какой-то другой цикл / цикл. Добавьте новый набор состояний, соответствующий циклу, и разрешите этому набору состояний представлять нечетные проходы через цикл / цикл (исходные состояния представляют четные проходы). При необходимости добавьте недетерминированность и используйте конструкцию powerset, чтобы превратить NFA обратно в DFA.
В любом случае, вы получите DFA для того же языка, который имеет больше состояний.