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

9

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:

entrez la description de l'image ici

De même, DFA acceptant des nombres binaires divisibles par 3 peut être formé comme suit: entrez la description de l'image ici

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 ?nk

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 2k{1,10,100,1000,...}10entrez la description de l'image ici

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 n3k2n nnkn

Maha
la source
Je pense que vous avez la réponse ici
3
@Raphael, non, c'est pour les multiples de ; il s'agit de pouvoirs de . nnn
DW
FYI il peut y avoir d' autres « à proximité » fonctions calculables par DFA tels que la divisibilité des pouvoirs , etc. , par exemple la fonction Collatz (qui implique des pouvoirs de 3) peut être calculé par un état transducteur etc fini
VZN

Réponses:

10

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 nL3n

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 , |LwL|w|pw=xyzi 0 x y i z L x y z | x | , | y | , | z | w w = 3 k 0 k 0N w =|y|1,|xy|pi0 xyizLxyz|x|,|y|,|z|ww=3k0k0N. En même temps, nous avons numériquement . Ainsi, nous avonsw=z+2|z|y+2|z|+|y|x

z+2|z|y+2|z|+|y|x=3k0

Maintenant, pomper pour obtenir pour touti 0wi0

z+2|z|y(j=0i1(2|y|)j)+2|z|+i|y|x=3ki,

où . Simplifier nous obtenons pouri 1k0<k1<k2<i1

z+2|z|y(2i|y|1)/(2|y|1)+2|z|+i|y|x=3ki.

Soit . Ensuite nous avonsC=z2|z|y/(2|y|1)

3ki=2|z|+i|y|y/(2|y|1)+2|z|+i|y|x+C.

Maintenant, observez que

3ki3ki1=(2|y|1)(3ki1C).

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)=3ki1(2|y|3kiki1).|2|y|3kiki1|13ki1ijeC(2|y|1)i

Denis Pankratov
la source
Pourriez-vous nous expliquer un peu pourquoi est vrai? Je demande parce que cette inégalité seule pourrait être utilisée pour atteindre une contradiction: , en multipliant les deux côtés par , nous obtenons , donc, , ce qui est une contradiction (pour la raison indiquée dans votre preuve). | 2 | y | - 3 k i -|2|y|3kiki1|13 k i - 1 | 3 k i - 1 2 | y | -3 k i | 3 k i - 1 ||2|y|3kiki1|13ki1|3ki12|y|3ki|3ki1|C(2|y|1)|3ki1
Anton Trunov
1
Depuis , nous avons que est pair et est impair. Leur différence est impaire, donc au moins 1 en valeur absolue. 2 | y | 3 k i - k i - 1|y|12|y|3kiki1
Denis Pankratov
10

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ératrice3L3

k=0nkzk ,

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 ) LnkkLp(x)/q(x)Ln k + p + 1 = a 0 n k + + a p n k + p p N a 1 , , a pZnknk+p+1=a0nk++apnk+ppNa1,,apZ

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 , , nlog2(3)(1,2)nk{0,1}k(nk)k12pnk,,nk+p

Klaus Draeger
la source
8

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 } 2bbb{0,1,,b1}210 { 0 , 1 } 4 2 1 ( 00 ) 3 3 10 { 0 , 1 , 2 }210{0,1}421(00)33-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 5b,c>1r>1bcr8328=238=25

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 cbcbc

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 SS332S

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.

J.-E. Épingle
la source
Pourriez-vous corriger les références, s'il vous plaît? Maintenant, ils sont tous deux numérotés [1] & [1].
Anton Trunov