DFA para aceptar todas las cadenas binarias de potencia de forma de

Podemos formar DFA aceptando números binarios divisibles por .$n$

Por ejemplo, DFA que acepta números binarios divisibles por 2 se puede formar de la siguiente manera:

Del mismo modo, DFA que acepta números binarios divisibles por 3 se puede formar de la siguiente manera:

Podemos seguir un procedimiento bien definido para formar este tipo de DFA. Sin embargo, ¿puede haber algún procedimiento bien definido o mejor para decir lógica para formar DFA que acepten números de la forma ?$n^k$

Por ejemplo, consideremos que DFA acepta todos los números del formulario . Este idioma será { 1 , 10 , $2^k$ , Por tanto, tienen expresiones regulares 10 * . Podemos formar DFA de la siguiente manera: $\{1,10,100,1000,...\}$$10^*$

Traté de formar DFA para y similares? Pero no fue capaz de hacerlo. ¿O es solo que su patrón de$3^k$ equivalentes binarios era lo que hacía posible crear DFA yno podemos formar DFA aceptando todos los números binarios de la forma n k para un n específico?$2^n$$n^k$$n$

Aquí hay una prueba rápida y sucia usando Pumping Lemma que lenguaje $L$ consiste en en binario no es regular (nota: es regular si está representado en ternario, por lo que la representación es importante).$3^n$

Usaré la notación del artículo de Wikipedia sobre Pumping Lemma . Suponga por contradicción que es regular. Deje w ∈ L ser cualquier cadena con | w | ≥ p (longitud de bombeo). Al bombear Lemma, escriba w = x y z con | y | ≥ 1 , | x y | ≤ p y para todo i ≥ 0 x y i z ∈ L , y $L$$w \in L$$|w| \ge p$$w = x y z$$|y| \ge 1, |xy| \le p$$i \ge 0$ $xy^i z \in L$ . Escribiré , $x$$y$$z$ también para valores numéricos de partes correspondientes, y por sus longitudes en w . Numéricamente tenemos w = 3 k 0 para algunos k 0 ∈ N . Al mismo tiempo tenemos numéricamente w = z + 2 | z | y + 2 | z | + | y | x . Por lo tanto, tenemos$|x|, |y|, |z|$$w$$w = 3^{k_0}$$k_0 \in \mathbb{N}$$w = z + 2^{|z|} y + 2^{|z|+|y|}x$

Ahora, bombeemos para obtener todo i ≥ $w$$i \ge 0$

donde . Simplificando obtenemos para i ≥ $k_0 < k_1 < k_2 < \ldots$$i \ge 1$

Deje . Entonces nosotros tenemos$C = z - 2^{|z|} y / (2^{|y|}-1)$

Ahora observa que

Por lo tanto, tenemos Tenga en cuenta que | 2 | y | - 3 k i - k i - 1 | ≥ $C (2^{|y|}-1) = 3^{k_{i-1}} (2^{|y|} - 3^{k_i - k_{i-1}}).$$|2^{|y|} - 3^{k_i - k_{i-1}}| \ge 1$ . Por lo tanto, por un lado, el valor absoluto del lado derecho crece al menos , que va al infinito coni. Por otro lado,y es una constante. Esto da una contradicción.$3^{k_{i-1}}$$i$ es independiente de$C(2^{|y|}-1)$$i$

Una forma de ver que esto no es posible para (por ejemplo) el lenguaje de potencias de 3 en expansión binaria es considerar la función generadora$L$$3$

,$\sum_{k=0}^{\infty}n_kz^k$

donde es el número de palabras de longitud k en L . Se sabe que esta función es racional, es decir, un cociente p ( x ) / q ( x ) polinomios, para cualquier L regular . En particular, los números n k satisfacen una recurrencia lineal n k + p + 1 = a 0 n k + ⋯ + a p n k + p para algunos p ∈ $n_k$$k$$L$$p(x)/q(x)$$L$$n_k$$n_{k+p+1}=a_0n_k+\dots+a_{p}n_{k+p}$$p\in\mathbb{N}$ y .$a_1,\dots,a_p\in\mathbb{Z}$

Por otro lado, dado que es un número irracional en ( 1 , 2 ) , obtenemos que n k ∈ { 0 , 1 } para todo k , y la secuencia ( n k ) k ≥ 1 no es periódica . Esto da una contradicción, ya que después de como máximo 2 p pasos, los valores de n k , ... , n k $\log_2(3)$$(1,2)$$n_k\in\{0,1\}$$k$$(n_k)_{k\ge 1}$$2^p$$n_k,\dots,n_{k+p}$ tiene que repetir, y la recurrencia conduciría a un comportamiento periódico.

El resultado (difícil) de Cobham [2] proporciona una respuesta completa a su pregunta.

Dada una numeración base , se dice que un conjunto de números naturales es b -reconocible si las representaciones en la base b de sus elementos forman un lenguaje regular en el alfabeto { 0 , 1 , ⋯ , b - 1 } . Por lo tanto, como observó, el conjunto de potencias de 2 es 2 -reconocible ya que está representado por el conjunto regular 10 ∗ en el alfabeto { 0 , 1 } . Del mismo modo, el conjunto de potencias de 4 es $b$$b$$b$$\{0, 1, \dotsm, b-1\}$$2$$2$$10^*$$\{0,1\}$$4$$2$-reconocible - corresponde al conjunto regular - y el conjunto de potencias de 3 es 3 -reconocible - corresponde al conjunto regular 10 ∗ sobre el alfabeto { 0 , 1 , 2 } .$1(00)^*$$3$$3$$10^*$$\{0,1,2\}$

Se dice que un conjunto de números naturales es en última instancia periódico si es una unión finita de progresiones aritméticas.

Dos bases se dice que son multiplicativa dependiente de si hay un r > 1 tal que tanto b y c son potencias de r : por ejemplo 8 y 32 son dependientes multiplicativa desde 8 = 2 3 y 8 = 2 5 .$b, c > 1$$r > 1$$b$$c$$r$$8$$32$$8 = 2^3$$8 = 2^5$

Teorema [Cobham] Sea y c dos bases multiplicativa independientes. Si un conjunto es b -reconocible $b$$c$$b$$c$ -reconocible, entonces es, en última instancia, periódico.

En particular, que sea ​​el conjunto de poderes de 3 . Hemos visto que es 3 -reconocible. Si era también 2 -recognizable, sería en última instancia periódico, que ciertamente no es el caso de S .$S$$3$$3$$2$$S$

El teorema de Cobham condujo a muchas generalizaciones y desarrollos sorprendentes. Recomiendo la encuesta [1] si está interesado.

[1] V. Bruyère, G. Hansel, C. Michaux, R. Villemaire, Logic and -reconocible sets of integers, Journées Montoises (Mons, 1992). Toro. Belga Matemáticas. Soc. Simon Stevin 1 (1994), no. 2, 191-238. Corrección en no. 4, 577.$p$

[2] A. Cobham, secuencias de etiquetas uniformes, matemáticas. Teoría de sistemas 6 (1972), 164-192.