DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$ - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-23T15:38:59Z https://cs.stackexchange.com/feeds/question/52148 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/52148 9 DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$ anir123 https://cs.stackexchange.com/users/17040 2016-01-22T14:25:58Z 2016-01-23T19:07:50Z <p>We can form DFA accepting binary numbers divisible by $n$. </p> <p>For example DFA accepting binary numbers divisible by 2 can be formed as follows:</p> <p><a href="https://i.stack.imgur.com/ndI3Xm.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ndI3Xm.jpg" alt="enter image description here"></a></p> <p>Similarly DFA accepting binary numbers divisible by 3 can be formed as follows: <a href="https://i.stack.imgur.com/M8fEzm.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/M8fEzm.png" alt="enter image description here"></a></p> <p>We can follow a well defined procedure to form these types of DFAs. However can there be any well defined procedure or better to say logic for forming DFAs accepting numbers of of the form $n^k$?</p> <p>For example, let us consider DFA accepting all numbers of the form $2^k$. This language will be $\{1,10,100,1000,...\}$, thus have regex $10^*$. We can form DFA as follows: <a href="https://i.stack.imgur.com/pPeL1m.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/pPeL1m.jpg" alt="enter image description here"></a></p> <p>I tried forming DFA for $3^k$ and similar ones? But was not able to do so. Or is it just that its pattern of $2^n$ binary equivalents which was making it possible to create DFA and <strong>we cannot form DFA accepting all binary numbers of the form $n^k$ for specific $n$?</strong></p> https://cs.stackexchange.com/questions/52148/-/52151#52151 10 Answer by Denis Pankratov for DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$ Denis Pankratov https://cs.stackexchange.com/users/42371 2016-01-22T17:24:02Z 2016-01-22T17:24:02Z <p>Here is a quick and dirty proof using Pumping Lemma that language $L$ consisting of $3^n$ in binary is not regular (note: it is regular if represented in ternary, so representation is important).</p> <p>I will use the notation from <a href="https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages">Wikipedia article re Pumping Lemma</a>. Assume for contradiction that $L$ is regular. Let $w \in L$ be any string with $|w| \ge p$ (pumping length). By Pumping Lemma, write $w = x y z$ with $|y| \ge 1, |xy| \le p$ and for all $i \ge 0$ $xy^i z \in L$. I will write $x$, $y$, and $z$ also for numerical values of corresponding parts, and $|x|, |y|, |z|$ for their lengths in $w$. Numerically we have $w = 3^{k_0}$ for some $k_0 \in \mathbb{N}$. At the same time we have numerically $w = z + 2^{|z|} y + 2^{|z|+|y|}x$. Thus, we have</p> <p>$$z + 2^{|z|}y+2^{|z|+|y|} x = 3^{k_0}$$</p> <p>Now, let's pump $w$ to get for all $i \ge 0$</p> <p>$$z + 2^{|z|} y \left( \sum_{j=0}^{i-1} (2^{|y|})^j \right) + 2^{|z|+i|y|} x = 3^{k_i},$$</p> <p>where $k_0 &lt; k_1 &lt; k_2 &lt; \ldots$. Simplifying we get for $i \ge 1$</p> <p>$$z + 2^{|z|} y (2^{i |y|} - 1) / (2^{|y|}-1) + 2^{|z|+i|y|} x = 3^{k_i}.$$</p> <p>Let $C = z - 2^{|z|} y / (2^{|y|}-1)$. Then we have</p> <p>$$3^{k_i} = 2^{|z|+i |y|} y / (2^{|y|}-1) + 2^{|z|+i|y|} x + C.$$</p> <p>Now, observe that</p> <p>$$3^{k_i} - 3^{k_{i-1}} = (2^{|y|}-1)(3^{k_{i-1}} - C).$$</p> <p>Therefore, we have $C (2^{|y|}-1) = 3^{k_{i-1}} (2^{|y|} - 3^{k_i - k_{i-1}}).$ Note that $|2^{|y|} - 3^{k_i - k_{i-1}}| \ge 1$. Thus, on one hand, the absolute value of the right hand side grows at least as $3^{k_{i-1}}$, which goes to infinity with $i$. On the other hand $C(2^{|y|}-1)$ is independent of $i$ and is a constant. This gives a contradiction.</p> https://cs.stackexchange.com/questions/52148/-/52152#52152 10 Answer by Klaus Draeger for DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$ Klaus Draeger https://cs.stackexchange.com/users/2014 2016-01-22T17:24:39Z 2016-01-22T17:24:39Z <p>One way of seeing that this is not possible for (e.g.) the language $L$ of powers of $3$ in binary expansion is by considering the generating function </p> <p>$\sum_{k=0}^{\infty}n_kz^k$,</p> <p>where $n_k$ is the number of words of length $k$ in $L$. This function is known to be rational, i.e. a quotient $p(x)/q(x)$ polynomials, for any regular $L$. In particular, the numbers $n_k$ satisfy a linear recurrence $n_{k+p+1}=a_0n_k+\dots+a_{p}n_{k+p}$ for some $p\in\mathbb{N}$ and $a_1,\dots,a_p\in\mathbb{Z}$.</p> <p>On the other hand, since $\log_2(3)$ is an irrational number in $(1,2)$, we get that $n_k\in\{0,1\}$ for all $k$, and the sequence $(n_k)_{k\ge 1}$ is not periodic. This gives a contradiction, since after at most $2^p$ steps, the values of $n_k,\dots,n_{k+p}$ have to repeat, and the recurrence would then lead to periodic behaviour. </p> https://cs.stackexchange.com/questions/52148/-/52183#52183 8 Answer by J.-E. Pin for DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$ J.-E. Pin https://cs.stackexchange.com/users/9612 2016-01-23T16:07:34Z 2016-01-23T19:07:50Z <p>A complete answer to your question is provided by a (difficult) result of Cobham . </p> <p>Given a numeration base $b$, a set of natural numbers is said to be $b$-recognizable if the representations in base $b$ of its elements form a regular language on the alphabet $\{0, 1, \dotsm, b-1\}$. Thus, as you observed, the set of powers of $2$ is $2$-recognizable since it is represented by the regular set $10^*$ on the alphabet $\{0,1\}$. Similarly, the set of powers of $4$ is $2$-recognizable -- it corresponds to the regular set $1(00)^*$ -- and the set of powers of $3$ is $3$-recognizable -- it corresponds to the regular set $10^*$ over the alphabet $\{0,1,2\}$.</p> <p>A set of natural numbers is said to be <em>ultimately periodic</em> if it is a finite union of arithmetic progressions.</p> <p>Two bases $b, c &gt; 1$ are said to be <em>multiplicatively dependent</em> if there is an $r &gt; 1$ such that both $b$ and $c$ are powers of $r$: for instance $8$ and $32$ are multiplicatively dependent since $8 = 2^3$ and $8 = 2^5$. </p> <p><strong>Theorem</strong> [Cobham] Let $b$ and $c$ two multiplicatively independent bases. If a set is $b$-recognizable and $c$-recognizable, then it is ultimately periodic.</p> <p>In particular let $S$ be the set of powers of $3$. We have seen that it is $3$-recognizable. If it was also $2$-recognizable, it would be ultimately periodic, which is certainly not the case for $S$.</p> <p>Cobham's theorem led to many surprising generalisations and developments. I recommend the survey  if you are interested.</p> <p> V. Bruyère, G. Hansel, C. Michaux, R. Villemaire, Logic and $p$-recognizable sets of integers, Journées Montoises (Mons, 1992). <em>Bull. Belg. Math. Soc.</em> Simon Stevin 1 (1994), no. 2, 191--238. Correction in no. 4, 577.</p> <p> A. Cobham, Uniform tag sequences, <em>Math. Systems Theory</em> <strong>6</strong> (1972), 164--192.</p>