This is an exercise from old exam on formal languages that I don't know how to solve: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.?One fact that I know of and is somehow related (has DFA and primes in the statement) is:Any DFA recognizing language $\{0^n : n \text{ is not divisible by } p\}$ has at least $p$ states.This can be seen by observing that the language is infinite, hence any DFA must have a reachable cycle, from which some accepting state is reachable. And if that cycle had less than $p$ states, then because any number smaller than $p$ is coprime with $p$, we could loop sufficiently many times in that cycle and arrive at the aforementioned accepted state with a word $0^{kp}$ for some natural $k$ - a contradiction.Maybe it's possible to use this fact, or alter this proof somehow to make it fit for the theorem with $L_p$?--EDITI'm trying to solve it by Myhill-Nerode theorem, as Yuval Filmus suggested.So, the goal is to find $2p$ words $w_1, \ldots, w_{2p}$ that will be pairwise distinguishable. I don't have a good intuition here but let's define $w_i$ to be $rev(bin(i))$ for $i = 1, \ldots, 2p$ ($bin(a)$ gives a binary representation of number $a$, and $rev(w)$ reverses the word $w$). Let's take any $i \neq j$ that both belong to $L_p$, or both don't. Now the task becomes a bit number-theoretic -- adding a common suffix $x$ to these words changes their values such that $val(w_ix) = val(w_i) + 2^{length(w_i)-1}val(x)$ (and similarly for $j$), where $val(\cdot)$ gives value of binary string reading from LSB (so e.g. $val(01) = 2$).Now the question is: can we always find an appropriate $x$ that makes one of $w_ix, w_jx$ belong to $L_p$, and the other not? I don't know the answer to this question. Maybe I should use the fact, that $2$ is a multiplicative generator modulo $p$?
DFA, lower bound on number of states, language with primes and remainders
regular languages;automata;finite automata