DFA para aceitar todas as cadeias binárias de poder de forma de

Podemos formar o DFA aceitando números binários divisíveis por .$n$

Por exemplo, o DFA que aceita números binários divisíveis por 2 pode ser formado da seguinte maneira:

Da mesma forma, o DFA que aceita números binários divisíveis por 3 pode ser formado da seguinte maneira:

Podemos seguir um procedimento bem definido para formar esses tipos de DFAs. No entanto, pode haver algum procedimento bem definido ou, melhor dizendo, lógica para formar DFAs que aceitam números do formato ?$n^k$

Por exemplo, consideremos o DFA aceitando todos os números do formulário . Esta linguagem será { 1 , 10 , 100 , 1000 , . . . } , portanto, tenha a expressão regular 10 ∗ . Podemos formar o DFA da seguinte maneira: $2^k$$\{1,10,100,1000,...\}$$10^*$

Tentei formar DFA para e similares? Mas não foi capaz de fazê-lo. Ou é apenas o seu padrão de 2 n equivalentes binários que estava possibilitando a criação do DFA e não podemos formar o DFA aceitando todos os números binários do formato n k para n específico ?$3^k$$2^n$$n^k$$n$

Aqui está uma prova rápida e suja, usando o Lemma de Bombeamento, de que a linguagem composta por 3 n em binário, não é regular (nota: é regular se representada no ternário, portanto, a representação é importante).$L$$3^n$

Usarei a notação do artigo da Wikipedia sobre Pumping Lemma . Suponha por contradição que seja regular. Vamos w ∈ L ser qualquer cadeia com | w | ≥ p (comprimento de bombeamento). Ao bombear o lema, escreva w = x y z com | y | ≥ 1 , | x y | ≤ p e para todos os i ≥ 0 x y i z ∈ L . Vou escrever x , $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$$x$$y$, e também para valores numéricos das partes correspondentes, e | x | , | y | , | z | por seus comprimentos em w . Numericamente temos w = 3 k 0 para alguns k 0 ∈ N . Ao mesmo tempo, temos numericamente w = z + 2 | z | y + 2 | z | + | y | x . Assim, temos$z$$|x|, |y|, |z|$$w$$w = 3^{k_0}$$k_0 \in \mathbb{N}$$w = z + 2^{|z|} y + 2^{|z|+|y|}x$

Agora, vamos bombear para obter tudo o que ≥ $w$$i \ge 0$

onde . Simplificando chegamos a i ≥ $k_0 < k_1 < k_2 < \ldots$$i \ge 1$

Seja . Então nós temos$C = z - 2^{|z|} y / (2^{|y|}-1)$

Agora observe que

Portanto, temos Note que | 2 | y | - 3 k i - k i - 1 | ≥ 1 . Assim, por um lado, o valor absoluto do lado direito cresce pelo menos em 3 $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$ , que vai para o infinito comi. Por outro lado,C(2 | y | -1)é independente deie é uma constante. Isso dá uma contradição.$3^{k_{i-1}}$$i$$C(2^{|y|}-1)$$i$

Uma maneira de ver que isso não é possível (por exemplo) para a linguagem de potências 3 na expansão binária é considerar a função geradora$L$$3$

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

onde é o número de palavras de comprimento k em L . Sabe-se que esta função é racional, isto é, um quociente de polinômios p ( x ) / q ( x ) , para qualquer L regular . Em particular, os números n k satisfazem uma recorrência linear n k + p + 1 = a 0 n k + ⋯ + a p n k + p para alguns 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}$e .$a_1,\dots,a_p\in\mathbb{Z}$

Por outro lado, como é um número irracional em ( 1 , 2 ) , obtemos que n k ∈ { 0 , 1 } para todo k , e a sequência ( n k ) k ≥ 1 não é periódica . Isso contradiz, pois, após no máximo 2 p etapas, os 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}$ precisa repetir, e a recorrência levaria a um comportamento periódico.

Uma resposta completa para sua pergunta é fornecida por um resultado (difícil) de Cobham [2].

Dada uma base de numeração , é dito que um conjunto de números naturais é b- reconhecível se as representações na base b de seus elementos formarem uma linguagem regular no alfabeto { 0 , 1 , ⋯ , b - 1 } . Assim, como você observou, o conjunto de potências de 2 é 2 - reconhecível, pois é representado pelo conjunto regular 10 ∗ no alfabeto { 0 , 1 } . Da mesma forma, o conjunto de potências de 4 é $b$$b$$b$$\{0, 1, \dotsm, b-1\}$$2$$2$$10^*$$\{0,1\}$$4$$2$-reconhecível - corresponde ao conjunto regular - e o conjunto de potências de 3 é 3 -recognizável - corresponde ao conjunto regular 10 ∗ sobre o alfabeto { 0 , 1 , 2 } .$1(00)^*$$3$$3$$10^*$$\{0,1,2\}$

Diz- se que um conjunto de números naturais é basicamente periódico se for uma união finita de progressões aritméticas.

Diz-se que duas bases são dependentes multiplicativamente se houver um r > 1 de modo que b e c sejam potências de r : por exemplo, 8 e 32 são dependentes multiplicativamente desde 8 = 2 3 e 8 = 2 5 .$b, c > 1$$r > 1$$b$$c$$r$$8$$32$$8 = 2^3$$8 = 2^5$

Teorema [Cobham] Let e c duas bases multiplicativamente independentes. Se um conjunto é b -reconhecível e c -reconhecível, então é basicamente periódico.$b$$c$$b$$c$

$S$$3$$3$$2$$S$

O teorema de Cobham levou a muitas generalizações e desenvolvimentos surpreendentes. Eu recomendo a pesquisa [1] se você estiver interessado.

$p$

[2] A. Cobham, Sequências uniformes de etiquetas, Matemática. Teoria dos Sistemas 6 (1972), 164-192.