Нерегулярный язык

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

Казалось, что было, но поискал и не нашёл.

Пусть $L$ - язык алфавита $\{ 0,1 \}$, состоящий из всех двоичных записей степеней тройки (то есть $L = \{ 1, 11, 1001, \ldots \}$). Доказать, что $L$ не распознаётся никаким конечным автоматом.

[Legioner93]

Сделаю попытку доказательства. Прошло 8 месяцев, тема на 10 странице, а задачка-то оказалось вроде бы не сложной.
Уверен, у уважаемого Профессора Снэйпа решение было не такое аляповатое и длинное, но этого мы уже не узнаем.

Предположим, что язык распознаётся КА, то есть регулярен. Применим лемму о накачке для регулярных языков. Не вникая в структуру самих "накачанных" слов, посмотрим на их длины: $|xy^i z |$ образует бесконечную натуральную арифметическую прогрессию. С другой стороны, длина двоичной записи $3^n$ - это $\lfloor\log_2(3^n)\rfloor+1=\lfloor n \log_2{3}\rfloor +1$.

Проверим, может ли некоторая натуральная арифметическая прогрессия иметь в качестве своих членов $\lfloor n_k \log_2{3}\rfloor$
Прибавление единицы роли не играет, так как она при желании заносится в начальное значение : $f(\bullet)+1=ak+b \ \Leftrightarrow \ f(\bullet)=ak+(b-1)$

Докажем, что ряд значений $f(n)=\lfloor nx \rfloor$ не содержит арифметической прогрессии $\forall x \in \mathbb{R}\setminus\mathbb{Q}, x>1$. То есть никакие $f(n_1), f(n_2), f(n_3) \dots$ не являют собой арифметическую прогрессию $(n_1 < n_2 < n_3 < \dots)$.
Доказательство я нашел не без наводок nnosipov, ex-math, ИСН в этой теме.

1) Сначала доказательство для $\alpha \in \mathbb{R}\setminus\mathbb{Q}$ факта плотности на $(0,1)$ дробной части $\{\alpha k + \beta\}$. Тут $\beta$ роли не играет, из плотности $\{\alpha k\}$ тут же следует плотность $\{\alpha k + \beta\}$.

(Моё доказательство)

Так как мера иррациональности любого иррационального числа $\geq 2$ (Лемма Дирихле), то для приближения $\frac{m}{n}$ погрешность будет $\delta=\left|\alpha - \frac{m}{n}\right|< \frac{1}{n^2}$
Для несократимой дроби $\frac{m}{n}$ очевидно, что $\{k\frac{m}{n}\}$ равномерно разбивают $(0,1)$ на $n$ частей по $\frac{1}{n}$. Тогда для $\frac{1}{n}<\frac{\varepsilon}{3}$ найдётся такое $k<n$, что $\{k\frac{m}{n}\}$ попадает в любой интервал ширины $\frac{\varepsilon}{3}$. Учитывая, что $k\delta<\frac{1}{n}$, $\alpha$ попадёт в интервал ширины $\varepsilon$.

(Доказательство участника ex-math)

ex-math в сообщении #719210 писал(а):

Нужно для любого $\delta$ найти такое $N$, что $\{Nx\}$ будет меньше $\delta$. Тогда дробные доли кратных этого $Nx$ найдутся в $\delta$-окрестности любого числа из $[0,1]$.

Возьмем $m>1/\delta$. Тогда среди $0,\{x\},\{2x\},\dots,\{mx\}$ найдутся два числа с разностью меньше $\delta$. Разность соответствующих этим числам "кратностей" $x$ и надо взять за $N$.

2) Сформулируем теперь такое утверждение: $ \forall x \in \mathbb{R}\setminus\mathbb{Q}, \ \forall a,b \in \mathbb{N}, \ \forall \varepsilon > 0 \rightarrow \exists t,k \in \mathbb{N} : (b+ak - \varepsilon) < tx < (b+ak) $. Теперь то же самое на словах: взяв любую натуральную арифметическую последовательность с начальным значением $b$ и шагом $a$ и перебирая числа $x,2x,3x,\dots$ мы рано или поздно подберемся сколь угодно близко (слева на $\varepsilon$) к некоторому члену этой арифметической прогрессии. При этом $t$ и $k$ для каждого $\varepsilon$, конечно же, разные.

Доказательство: из пункта 1 тривиально следует, что $\exists s,k \in \mathbb{N}$, такие что $sx=k+\Delta$, где $\frac{b}{a}-\frac{\varepsilon}{a}<\Delta<\frac{b}{a}$, то есть $0<b-a \Delta<\varepsilon$.
Это так, потому что мы всегда можем взять такое $s$, чтобы $\{sx\}=\{\Delta\}$ (не для вообще любого $\Delta$, конечно, но какое-нибудь $\Delta$ из нужного нам интервала шириной в $\frac{\varepsilon}{a} обязательно найдется), и всегда можем отнять и прибавить некоторое натуральное число \lfloor \Delta \rfloor$;
$sx=\lfloor sx \rfloor + \{sx\}=(\lfloor sx \rfloor - \lfloor \Delta \rfloor) + (\lfloor \Delta \rfloor + \{\Delta\})=k+ \Delta$

Теперь несколько преобразований:
$\frac{b}{a}-\frac{\varepsilon}{a}<\Delta<\frac{b}{a}$

$\frac{b}{a}-\frac{\varepsilon}{a}<sx-k<\frac{b}{a}$

$b-\varepsilon<asx-ak<b$

$b+ak-\varepsilon<asx<b+ak$, $t=as$

$b+ak-\varepsilon<tx<b+ak$

3) Доказательство исходной теоремы.
Для любого $x>1$ получаем, что $(t+1)x>b+ak+1$ (для этого нужно взять достаточно маленькую $\varepsilon$)
То есть $\lfloor tx \rfloor=b+ak-1$, а $\lfloor (t+1)x \rfloor=b+ak+1$, поэтому для некоторого $k \in \mathbb{N}$
$\nexists n \in \mathbb{N} : \lfloor nx \rfloor =b+ak$.

Поэтому язык нерегулярен.