Диаграмма состояний детерминированных конечных автоматов

Question

Мне нужно сделать DFA с 8 состояниями, которая принимает 0 и 1 и имеет четное число 1s и подстроку ... 000 ... где-то в ней. Поэтому я знаю, как найти подстроку 000, и я знаю, как найти четное число 1, но я не уверен, как это сделать. Есть ли формула или что-то для этого, я только начал DFA и NFA, поэтому я не совсем уверен, как решить эту проблему, кроме того, чтобы вытащить ее с проб и ошибок. Любая помощь будет большим

Answer 1

для тестирования даже количество единиц:

Тогда для тестирования 000 подстроку:

Тогда мы можем вычислить пересечение этих DFA, используя classical cross-product construction и получить (минимальный) DFA: