DFA pour accepter toutes les chaînes binaires de puissance de forme de

Nous pouvons former DFA en acceptant des nombres binaires divisibles par .$n$

Par exemple, DFA acceptant des nombres binaires divisibles par 2 peut être formé comme suit:

De même, DFA acceptant des nombres binaires divisibles par 3 peut être formé comme suit:

Nous pouvons suivre une procédure bien définie pour former ces types de DFA. Cependant, peut-il y avoir une procédure bien définie ou, pour mieux dire, une logique pour former des DFA acceptant des nombres de la forme ?$n^k$

Par exemple, considérons que DFA accepte tous les nombres de la forme . Cette langue sera , donc a regex . Nous pouvons former DFA comme suit: { 1 , 10 , 100 , 1000 , . . . } 10 $2^k$$\{1,10,100,1000,...\}$$10^*$

J'ai essayé de former DFA pour et similaires? Mais n'a pas pu le faire. Ou est-ce simplement que son modèle de équivalents binaires qui permettait de créer DFA et que nous ne pouvons pas former DFA en acceptant tous les nombres binaires de la forme pour spécifique ?2 $3^k$$2^n$$n^k$$n$

Voici une preuve rapide et sale en utilisant le lemme de pompage que le langage composé de en binaire n'est pas régulier (note: il est régulier s'il est représenté en ternaire, donc la représentation est importante).3 $L$$3^n$

J'utiliserai la notation d'un article de Wikipédia sur le lemme de pompage . Supposons par contradiction que est régulier. Soit une chaîne quelconque avec (longueur de pompage). En pompant le lemme, écrivez avec et pour tout . J'écrirai également , et pour les valeurs numériques des parties correspondantes, etpour leurs longueurs en . Numériquement, nous avons pour certainsw ∈ L | w | ≥ p w = x y z | y | ≥ 1 , $L$$w \in L$$|w| \ge p$$w = x y z$i ≥ 0 x y i z ∈ L x y z | x | , | y | , | z | w w = 3 k 0 k 0 ∈ N w $|y| \ge 1, |xy| \le p$$i \ge 0$ $xy^i z \in L$$x$$y$$z$$|x|, |y|, |z|$$w$$w = 3^{k_0}$$k_0 \in \mathbb{N}$. En même temps, nous avons numériquement . Ainsi, nous avons$w = z + 2^{|z|} y + 2^{|z|+|y|}x$

Maintenant, pomper pour obtenir pour touti ≥ $w$$i \ge 0$

où . Simplifier nous obtenons pouri ≥ $k_0 < k_1 < k_2 < \ldots$$i \ge 1$

Soit . Ensuite nous avons$C = z - 2^{|z|} y / (2^{|y|}-1)$

Maintenant, observez que

Par conséquent, nous avonsNotez que . Ainsi, d'une part, la valeur absolue du côté droit croît au moins de , qui va à l'infini avec . Par contre est indépendant de et est une constante. Cela donne une contradiction.| 2 | y | -3 k i - k i - 1 | ≥13 k i - 1 iC(2 | y |$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$$3^{k_{i-1}}$$i$$C(2^{|y|}-1)$$i$

Une façon de voir que cela n'est pas possible pour (par exemple) le langage de puissances de en expansion binaire est de considérer la fonction génératrice$L$$3$

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

où est le nombre de mots de longueur dans . Cette fonction est connue pour être rationnelle, c'est-à-dire un quotient polynômes, pour tout régulier . En particulier, les nombres satisfont une récurrence linéaire pour certains et . k L p ( x ) / q ( x ) $n_k$$k$$L$$p(x)/q(x)$$L$n k + p + 1 = a 0 n k + ⋯ + a p n k + p p ∈ N a 1 , … , a p ∈ $n_k$$n_{k+p+1}=a_0n_k+\dots+a_{p}n_{k+p}$$p\in\mathbb{N}$$a_1,\dots,a_p\in\mathbb{Z}$

En revanche, comme est un nombre irrationnel dans , nous obtenons ce pour tout , et la séquence n'est pas périodique. Cela donne une contradiction, car après au plus pas, les valeurs de doivent se répéter, et la récurrence entraînerait alors un comportement périodique.( 1 , 2 ) n k ∈ { 0 , 1 } k ( n k ) k ≥ 1 2 p 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}$

Une réponse complète à votre question est fournie par un résultat (difficile) de Cobham [2].

Étant donné une base de numérotation , un ensemble de nombres naturels est dit reconnaissable si les représentations en base de ses éléments forment un langage régulier sur l'alphabet . Ainsi, comme vous l'avez observé, l'ensemble des puissances de est reconnaissable puisqu'il est représenté par l'ensemble régulier sur l'alphabet . De même, l'ensemble des puissances de est - reconnaissable - il correspond à l'ensemble régulier - et l'ensemble des puissances de estb b { 0 , 1 , ⋯ , b - 1 } $b$$b$$b$$\{0, 1, \dotsm, b-1\}$$2$10 ∗ { 0 , 1 } 4 2 1 ( 00 ) ∗ 3 3 10 ∗ { 0 , 1 , 2 $2$$10^*$$\{0,1\}$$4$$2$$1(00)^*$$3$$3$-reconnaissable - il correspond à l'ensemble régulier sur l'alphabet .$10^*$$\{0,1,2\}$

On dit qu'un ensemble de nombres naturels est finalement périodique s'il s'agit d'une union finie de progressions arithmétiques.

Deux bases sont dites dépendantes multiplicativement s'il y a un tel que et sont des puissances de : par exemple et sont dépendants multiplicativement puisque et .r > 1 b c r 8 32 8 = 2 3 8 = 2 $b, c > 1$$r > 1$$b$$c$$r$$8$$32$$8 = 2^3$$8 = 2^5$

Théorème [Cobham] Soit et deux bases indépendantes multiplicativement. Si un ensemble est reconnaissable et reconnaissable, il est finalement périodique.c b $b$$c$$b$$c$

En particulier, soit l'ensemble des pouvoirs de . Nous avons vu qu'il est reconnaissable. Si elle était également -recognizable, ce serait en fin de compte périodique, ce qui est certainement pas le cas pour .3 3 2 $S$$3$$3$$2$$S$

Le théorème de Cobham a conduit à de nombreuses généralisations et développements surprenants. Je recommande l'enquête [1] si vous êtes intéressé.

[1] V. Bruyère, G. Hansel, C. Michaux, R. Villemaire, Logique et ensembles d'entiers reconnaissables, Journées Montoises (Mons, 1992). Taureau. Belg. Math. Soc. Simon Stevin 1 (1994), no. 2, 191--238. Correction en no. 4, 577.$p$

[2] A. Cobham, Séquences d'étiquette uniformes, Math. Systems Theory 6 (1972), 164-192.