Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

# Return to Revisions

2 of 5 edited tags

# DFA, lower bound on number of states, language with primes and remainders

Let $$p \ge 5$$ be a prime number and $$L_p$$ be a language of words over $$\{0,1\}$$ that read in binary from right (i.e. from least significant bit) give a number that gives remainder modulo $$p$$ from the set $$\{1,2, \ldots, \frac{p-1}{2}\}$$.

How to show that:

Every DFA recognizing $$L_p$$ has at least $$2p$$ states.

?

 asked Aug 27 '16 at 9:45 socumbersome 8566 bronze badges