CODEWITHSUNDEEP
finite-automatadfacomputation-theory
Prashant Bhardwaj
Prashant Bhardwaj

Reputation: 1213

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

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}.

Upvotes: 0

Views: 4132

Answers (2)

No Name Needed
No Name Needed

Reputation: 13

No of state will be 2^n where n is nth symbol from right So 2^5=32 will be no of states

Upvotes: -1

Jim Lewis
Jim Lewis

Reputation: 45075

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 25 = 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.

Upvotes: 3

Related Questions