Для подобных проблем, когда DFA имеет много принимающих состояний, часто полезно подумать о том, какие строки DFA отклоняет , а не что принимает.
В в этом случае отклоняются только состояния q2 и q4, а язык, описываемый отклонениями, является более простым. Чтобы добраться до q2, вам нужно 000*. Чтобы перейти к q4, вам нужно 000*10* или 0100* или 1000*.
. Таким образом, строки, которые отклоняются, имеют по крайней мере 2 0 с и самое большее 1.
Er go, допускаются строки, имеющие два или более 1 с или не более одного 0. Обратите внимание, что это описание охватывает пустую строку и короткие строки, такие как 1, 0, 01, 10 и 11 (все они имеют не более одного 0).