Теорема Майхилла-Нерода является полезным инструментом для решения подобных проблем.
Идея состоит в том, чтобы создать набор классов эквивалентности строк, используя идею "различения расширений". Рассмотрим две строки x и y. Если существует строка z
так что в языке точно один из xz и yz, то z является отличительным расширением,
и x и y должны принадлежать различным классам эквивалентности. Каждый класс эквивалентности отображается в другое состояние в минимальном DFA.
Для языка, который вы описали, пусть x и y - любая пара разных 5-символьных строк
более {0,1}. Если они отличаются в позиции n (считая справа, начиная с 1), то любая строка z длиной 5-n будет отличительным расширением: если x имеет 0 в позиции n,
и у имеет 1 в положении n, тогда xz отклоняется и yz принимается. Это дает 2 5 = 32
классы эквивалентности.
Если s - строка длиной k <5 символов, она принадлежит одному и тому же классу эквивалентности
как 0 <sup>(5-k) s (то есть добавьте 0-отступ слева до длины 5 символов).
Если s - строка длиной k> 5 символов, ее класс эквивалентности определяется ее последними 5 символами.
Следовательно, все строки над {0,1} попадают в один из 32 классов эквивалентности, описанных выше, и по теореме Майхилла-Нерода минимальный DFA для этого языка имеет 32 состояния.