Задача на конечные автоматы

[PreVory]

Пусть B-некоторое подмножество множества натуральных чисел. Назовём языком $\L_k(B)$ множество чисел языка B записанных в k-ичной системе счисления.
Доказать что существует такое множество B, что $\L_2(B)$ регулярный а $\L_3(B)$ не регулярный.
Доказать в общем виде от противного не получается изза того что возможны 2 варианта когда условие не верно, так что видимо нужно искать конструктивное доказательство. Перебирал множества для которых регулярность $\L_2(B)$ или не регулярность $\L_3(B)$ очевидна, но тогда второе условие не верно или не представляется возможным доказать.

[Профессор Снэйп]

$$ B = \{ 2^k : k \in \mathbb{N} \} $$

[PreVory]

Ну в принципе понятно, что для этого языка $\L_3(B)$ скорее всего будет не регулярным, однако доказать это использую отрицание леммы о разрастании не удаётся.

[Профессор Снэйп]

PreVory в сообщении #358288 писал(а):

...однако доказать это использую отрицание леммы о разрастании не удаётся.

Странно. "Лемма о разрастании" истинна, значит, её отрицание ложно. А из ложного утверждения доказывается всё, что угодно

[Профессор Снэйп]

Вообще тут лемма о накачке нормально работает.

Пусть $\sum_{i=0}^n d_i 3^i$ --- достаточно большая степень двойки и $d_i \in \{ 0,1,2 \}$. Найдутся $0 \leqslant l < k \leqslant n$, такие что число

$$ F(s) = \sum_{i=0}^{l-1} d_i 3^i + \sum_{j=1}^s \sum_{i=l}^{k-1} d_i 3^{i+(k-l)(j-1)} + \sum_{i=k}^n d_i 3^{i + (s-1)(k-l)} $$

является степенью двойки при любом натуральном $s$. Из третьего слагаемого выносим $3^{(k-l)s}$, второе расписываем как сумму геометрической прогрессии, получаем

$$ F(s) = \sum_{i=0}^{l-1} d_i 3^i + \frac{3^{(k-l)s}-1}{3^{k-l}-1} \sum_{i=l}^{k-1} d_i 3^i + 3^{(k-l)s} \sum_{i=k}^n d_i 3^{i - (k-l)}. $$

Пусть

$$ A = \frac{1}{3^{k-l}-1} \sum_{i=l}^{k-1} d_i 3^i + \sum_{i=k}^n d_i 3^{i-(k-l)} $$

и

$$ B = \sum_{i=0}^{l-1} d_i 3^i - \frac{1}{3^{k-l}-1} \sum_{i=l}^{k-1} d_i 3^i. $$

Имеем $F(s) = 3^{(k-l)s}A + B$, $F(s+1) = 3^{k-l}F(s) + (1 - 3^{k-l})B$ и

$$ \lim_{s \to \infty} \frac{F(s+1)}{F(s)} = 3^{k-l} + \lim_{s \to \infty} \frac{(1-3^{k-l})B}{F(s)} = 3^{k-l}. $$

Однако $F(s+1)/F(s)$ при любом $s$ является степенью двойки. Противоречие.