5
$\begingroup$

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$?

--EDIT

I'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$?

$\endgroup$
  • 1
    $\begingroup$ Use Myhill–Nerode theory. Note that if you were reading the number MSB first, you would need only $p$ states. $\endgroup$ – Yuval Filmus Aug 27 '16 at 14:43
  • $\begingroup$ @YuvalFilmus - I added an attempt to use Myhill-Nerode theorem but got stuck along the way. $\endgroup$ – socumbersome Aug 27 '16 at 21:56
  • $\begingroup$ You should keep trying. We're not going to solve this for you here. It's your exercise, after all. $\endgroup$ – Yuval Filmus Aug 27 '16 at 23:53
  • $\begingroup$ @YuvalFilmus - as to your first comment -- do you mean that proof should be a bit indirect? That is, to show using Myhill-Nerode theorem that reading from MSB would require $p$ states, and then using this fact alone conclude that reading from LSB would definitely be twice as much? $\endgroup$ – socumbersome Aug 28 '16 at 8:00
  • 1
    $\begingroup$ No, I just mean that there is something extra that happens when you read from the LSB, which is that you need to keep track of your position (mod 2). That's where the doubling comes from. $\endgroup$ – Yuval Filmus Aug 28 '16 at 14:54
0
$\begingroup$

For a binary string $x$, let $N(x)$ be the value of the number when read LSB first. Then $N(xy) = N(x) + 2^{|x|} N(y)$.

Now consider any $P \subseteq \mathbb{Z}_p$. For any $x$, $N(xy) \bmod p \in P$ iff $N(x) + 2^{|x|} N(y) \bmod p \in P$. This condition depends only on $N(x) \bmod p$ and $2^{|x|} \bmod p$, i.e. on $N(x) \bmod p$ and $|x| \bmod \operatorname{ord}_p(2)$ (here $\operatorname{ord}_p(2)$ is the smallest exponent such that $2^o \equiv 1 \pmod{p}$).

As $x$ goes over all binary strings, $(N(x) \bmod{p}, |x| \bmod\operatorname{ord}_p(2))$ goes over all possible $p \cdot \operatorname{ord}_p(2)$ values. One way to see this is to take zero paddings of strings representing $0,\ldots,p-1$.

Let us now consider the particular $P$ stated in the question. Since $p \geq 5$, $2^2 \not\equiv 1 \pmod{p}$, and so to prove the claim, it suffices to show that the equivalence classes $\{(a,1),(a,2) : a \in \mathbb{Z}_p\}$ are all different.

Consider any two equivalence classes $(a_1,b_1),(a_2,b_2)$. If exactly one of $a_1,a_2$ is in $P$, then there is nothing to do. Suppose first that $a_1,a_2 \in \{1,\ldots,\frac{p-1}{2}\}$. If $b_1 = b_2$ then $a_1 \neq a_2$. Without loss of generality, $a_1 < a_2$. Therefore we can find $n$ such that $a_1 + nb_1 = \frac{p-1}{2}$ while $a_2 + nb_2 \notin P$. If $b_1 = 1$ and $b_2 = 2$ then there is a range of $\frac{p-1}{2}$ consecutive values of $n$ such that $a_1 + nb_1$ goes over all of $1,\ldots,\frac{p-1}{2}$. For the same values of $n$, the expression $a_2 + nb_2$ goes over $\frac{p-1}{2}$ values in jumps of $2$; it is not hard to check that not all of them can belong to $P$.

We leave the case $a_1,a_2 \notin P$ to the reader.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.