Timeline for DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 23, 2016 at 14:55 | comment | added | Denis Pankratov | Since $|y| \ge 1$, we have that $2^{|y|}$ is even and $3^{k_i - k_{i-1}}$ is odd. Their difference is odd, therefore at least 1 in absolute value. | |
| Jan 23, 2016 at 9:04 | comment | added | Anton Trunov | Could you elaborate a little bit on why $|2^{|y|} - 3^{k_i - k_{i-1}}| \ge 1$ is true? I'm asking because this inequality alone could be used to reach a contradiction: $|2^{|y|} - 3^{k_i - k_{i-1}}| \ge 1$, multiplying both sides of it by $3^{k_{i-1}}$, we get $|3^{k_{i-1}} 2^{|y|} - 3^{k_i}| \ge 3^{k_{i-1}}$, thus, $|C (2^{|y|} - 1)| \ge 3^{k_{i-1}}$, which is a contradiction (by the reason provided in your proof). | |
| Jan 22, 2016 at 17:24 | history | answered | Denis Pankratov | CC BY-SA 3.0 |