DFA, lower bound on number of states, language with primes and remainders - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T14:04:00Z https://cs.stackexchange.com/feeds/question/62934 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/62934 5 DFA, lower bound on number of states, language with primes and remainders socumbersome https://cs.stackexchange.com/users/18030 2016-08-27T09:45:35Z 2019-08-20T21:03:10Z <p>This is an exercise from old exam on formal languages that I don't know how to solve:</p> <p>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}\}$.</p> <p>How to show that:</p> <blockquote> <p>Every DFA recognizing $L_p$ has at least $2p$ states.</p> </blockquote> <p>?</p> <p>One fact that I know of and is somehow related (has DFA and primes in the statement) is:</p> <blockquote> <p>Any DFA recognizing language $\{0^n : n \text{ is not divisible by } p\}$ has at least $p$ states.</p> </blockquote> <p>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.</p> <p>Maybe it's possible to use this fact, or alter this proof somehow to make it fit for the theorem with $L_p$?</p> <p>--<strong>EDIT</strong></p> <p>I'm trying to solve it by Myhill-Nerode theorem, as Yuval Filmus suggested.<br> 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$).<br> 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$?</p> https://cs.stackexchange.com/questions/62934/-/105958#105958 0 Answer by Yuval Filmus for DFA, lower bound on number of states, language with primes and remainders Yuval Filmus https://cs.stackexchange.com/users/683 2019-03-23T18:22:35Z 2019-03-23T18:22:35Z <p>For a binary string <span class="math-container">$x$</span>, let <span class="math-container">$N(x)$</span> be the value of the number when read LSB first. Then <span class="math-container">$N(xy) = N(x) + 2^{|x|} N(y)$</span>.</p> <p>Now consider any <span class="math-container">$P \subseteq \mathbb{Z}_p$</span>. For any <span class="math-container">$x$</span>, <span class="math-container">$N(xy) \bmod p \in P$</span> iff <span class="math-container">$N(x) + 2^{|x|} N(y) \bmod p \in P$</span>. This condition depends only on <span class="math-container">$N(x) \bmod p$</span> and <span class="math-container">$2^{|x|} \bmod p$</span>, i.e. on <span class="math-container">$N(x) \bmod p$</span> and <span class="math-container">$|x| \bmod \operatorname{ord}_p(2)$</span> (here <span class="math-container">$\operatorname{ord}_p(2)$</span> is the smallest exponent such that <span class="math-container">$2^o \equiv 1 \pmod{p}$</span>).</p> <p>As <span class="math-container">$x$</span> goes over all binary strings, <span class="math-container">$(N(x) \bmod{p}, |x| \bmod\operatorname{ord}_p(2))$</span> goes over all possible <span class="math-container">$p \cdot \operatorname{ord}_p(2)$</span> values. One way to see this is to take zero paddings of strings representing <span class="math-container">$0,\ldots,p-1$</span>.</p> <p>Let us now consider the particular <span class="math-container">$P$</span> stated in the question. Since <span class="math-container">$p \geq 5$</span>, <span class="math-container">$2^2 \not\equiv 1 \pmod{p}$</span>, and so to prove the claim, it suffices to show that the equivalence classes <span class="math-container">$\{(a,1),(a,2) : a \in \mathbb{Z}_p\}$</span> are all different.</p> <p>Consider any two equivalence classes <span class="math-container">$(a_1,b_1),(a_2,b_2)$</span>. If exactly one of <span class="math-container">$a_1,a_2$</span> is in <span class="math-container">$P$</span>, then there is nothing to do. Suppose first that <span class="math-container">$a_1,a_2 \in \{1,\ldots,\frac{p-1}{2}\}$</span>. If <span class="math-container">$b_1 = b_2$</span> then <span class="math-container">$a_1 \neq a_2$</span>. Without loss of generality, <span class="math-container">$a_1 &lt; a_2$</span>. Therefore we can find <span class="math-container">$n$</span> such that <span class="math-container">$a_1 + nb_1 = \frac{p-1}{2}$</span> while <span class="math-container">$a_2 + nb_2 \notin P$</span>. If <span class="math-container">$b_1 = 1$</span> and <span class="math-container">$b_2 = 2$</span> then there is a range of <span class="math-container">$\frac{p-1}{2}$</span> consecutive values of <span class="math-container">$n$</span> such that <span class="math-container">$a_1 + nb_1$</span> goes over all of <span class="math-container">$1,\ldots,\frac{p-1}{2}$</span>. For the same values of <span class="math-container">$n$</span>, the expression <span class="math-container">$a_2 + nb_2$</span> goes over <span class="math-container">$\frac{p-1}{2}$</span> values in jumps of <span class="math-container">$2$</span>; it is not hard to check that not all of them can belong to <span class="math-container">$P$</span>.</p> <p>We leave the case <span class="math-container">$a_1,a_2 \notin P$</span> to the reader.</p>