Bumped by Community user occurred Aug 20 at 21:03 Bumped by Community user occurred Apr 22 at 20:03 Tweeted twitter.com/StackCompSci/status/841879262454005760 occurred Mar 15 '17 at 5:10 5 added an attempt to solve problem edited Aug 27 '16 at 21:54 socumbersome 8566 bronze badges 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$$? 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$$? 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$$? 4 edited tags | link edited Aug 27 '16 at 11:30 socumbersome 8566 bronze badges 3 added info about problem's origin and an attempt to solve it edited Aug 27 '16 at 11:24 socumbersome 8566 bronze badges 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$$? 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. ? 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$$? 2 edited tags | link edited Aug 27 '16 at 10:30 Raphael♦ 59k2525 gold badges144144 silver badges327327 bronze badges 1 asked Aug 27 '16 at 9:45 socumbersome 8566 bronze badges