Minimum number of states in a DFA having '1' as the 5th symbol from right

Question

What is the minimum number of states needed in a DFA to accept the strings having '1' as 5th symbol from right? Strings are defined over the alphabet {0,1}.

Answer 1

The Myhill-Nerode theorem is a useful tool for solving these sorts of problems.

The idea is to build up a set of equivalence classes of strings, using the idea of "distinguishing extensions". Consider two strings x and y. If there exists a string z such that exactly one of xz and yz is in the language, then z is a distinguishing extension, and x and y must belong to different equivalence classes. Each equivalence class maps to a different state in the minimal DFA.

For the language you've described, let x and y be any pair of different 5-character strings over {0,1}. If they differ at position n (counting from the right, starting at 1), then any string z with length 5-n will be a distinguishing extension: if x has a 0 at position n, and y has a 1 at position n, then xz is rejected and yz is accepted. This gives 2⁵ = 32 equivalence classes.

If s is a string with length k < 5 characters, it belongs to the same equivalence class as 0^(5-k)s (i.e. add 0-padding to the left until it's 5 characters long).

If s is a string with length k > 5 characters, its equivalence class is determined by its final 5 characters.

Therefore, all strings over {0,1} fall into one of the 32 equivalence classes described above, and by the Myhill-Nerode theorem, the minimal DFA for this language has 32 states.