2 of 5
edited tags
Raphael
  • 72.3k
  • 29
  • 179
  • 389

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.

?