Langage des valeurs d'une fonction affine

10

Écrivez pour l'expansion décimale de (sans interligne ). Soit et entiers, avec . Considérez le langage des expansions décimales des multiples de plus une constante:ˉ nn¯ nn0aabba>0a>0aa

M = { ¯ ax + bxN}

M={ax+b¯¯¯¯¯¯¯¯¯¯¯¯¯¯xN}

est-il régulier? sans contexte?MM

(Contraste avec la langue du graphique d'une fonction affine )

Je pense que cela ferait une bonne question de devoirs, donc les réponses qui commencent par un indice ou deux et expliquent non seulement comment résoudre la question mais aussi comment décider quelles techniques utiliser seraient appréciées.

Gilles 'SO- arrête d'être méchant'
la source
Je me rends compte tout à l'heure que j'en ai répondu à un cas précis, en suivant l'idée de @vonbrand. DFA qui accepte les représentations décimales d'un nombre naturel divisible par 43
Hendrik

Réponses:

9

Très simple: supposons que les nombres soient écrits en décimal (les autres bases sont gérées par une modification triviale). Construire un DFA, avec états 0, 1, ..., . L'état de départ est 0 et à partir de l'état en entrée, le chiffre passe à l'état . L'état d'acceptation est (peut nécessiter une modification si ).a a - 1 q d ( 10 q + d ) mod a b mod a b > aaa1qd(10q+d)modabmodab>a

vonbrand
la source
1
Très bien - bien mieux que le mien!
David Lewis
8

C'est régulier. Travaillons d'abord en binaire, qui généralisera à n'importe quelle base> 1. Soit le langage en question. Pour a = 1, b = 0 on obtientM a , bMa,b

M 1 , 0 = { 1 , 10 , 11 , 100 , 101 , . . . }M1,0={1,10,11,100,101,...}

qui est toutes les chaînes sur sans zéros non significatifs, ce qui est régulier (construisez une expression régulière pour cela).{ 0 , 1 }{0,1}

Maintenant pour tout , avec b toujours 0, nous obtenons de en multipliant numériquement par a, c'est-à-dire en effectuant la transformation sur chaque chaîne de . Cela peut être fait au niveau du bit par une séquence de décalages et d'additions de qui dépendent des bits de la chaîne fixe . Les deux transformations dont nous avons besoin sont:a M a , 0 M 1 , 0 ˉ x¯ a x M a , 0 x ˉ aaMa,0M1,0x¯ax¯¯¯¯¯¯Ma,0xa¯

ˉ x ¯ 2 x ˉ x ˉ x 0x¯2x¯¯¯¯¯ qui estx¯x¯0

et

ˉ x ¯ 2 x + xx¯2x+x¯¯¯¯¯¯¯¯¯¯¯¯¯¯

La concaténation d'un 0 à droite préserve clairement la régularité. Il suffit donc de prouver que la deuxième opération conserve la régularité. Pour ce faire, un transducteur à états finis fonctionne sur de droite à gauche. C'est l'étape la plus difficile. Je suggère de le faire avec un programme de pseudo-code et de la mémoire auxiliaire finie (comme certaines variables de bits) plutôt que d'utiliser des états. Tant que la mémoire est d'une taille fixe sur toutes les entrées et que vous balayez strictement de droite à gauche, c'est une transduction à états finis et conserve la régularité.ˉ xx¯

Enfin, pour obtenir de nous devons ajouter numériquement à chaque chaîne, mais cela se fait avec un transducteur similaire qui dépend du nombre fixe b.M a , b M a , 0 b T bMa , bMa , 0bTb

Pour faire de même dans n'importe quelle base, montrez en plus comment effectuer la multiplication par un seul chiffre dans cette base, en utilisant un transducteur qui dépend de d. Avec cela, nous pouvons multiplier par des nombres à plusieurs chiffres et rester dans les langues régulières. Ou, nous pouvons affiner cela en disant que la multiplication par est simplement une addition répétée.d S d dS

Vous ne vouliez que des indices. Chacune de ces étapes dépend d'un théorème / technique assez complexe, donc prouver à ceux-ci d'obtenir une preuve complète sera le travail supplémentaire.

David Lewis
la source
Votre FA n'obtient pas en entrée, donc je ne vois pas comment ce que vous écrivez montre que la langue actuelle est régulière. Notez que tous les programmes qui utilisent une mémoire finie ne correspondent pas à FA: il est important de ne pouvoir aller qu'une seule fois et de gauche à droite sur l'entrée, en considérant chaque symbole d'entrée exactement une fois. ˉ xX¯
Raphael
@Raphael Vous pouvez aller de droite à gauche si vous le souhaitez, ce qui compte, c'est d'être cohérent. Je ne trouve pas de défaut dans l'esquisse de preuve de David; invoquer des transducteurs est un peu moins élémentaire que ce que j'imaginais, mais il semble valide.
Gilles 'SO- arrête d'être méchant'
@ Gilles: Tout d'abord, il n'explique pas comment entrelacer la multiplication par et ajouter au résultat en une seule passe ; il réduit même la multiplication de à "une séquence de décalages et d'additions de ". Chaque changement et ajout est bien, mais comment faire la séquence? Deuxièmement, et plus important encore, il montre comment construire un transducteur qui calcule ; cela ne pas vous donner immédiatement une FA qui accepte . Par exemple, la multiplication des nombres est facile mais l'affacturage ne l'est pas (prétendument). Vous avez donc besoin d'au moins un argument supplémentaire. a b a x ˉ x¯ a x + b MunebuneX X¯a x + b¯¯¯¯¯¯¯¯¯¯¯¯¯¯ M
Raphael
Je ne construis pas de FSA. Je commence par un ensemble facilement démontré comme régulier ( ), puis je transforme toutes les chaînes en lui avec une série finie d'opérations, chacune préservant la régularité. Cela nécessite un certain nombre de passes (transducteurs). Mais c'est OK, car la séquence des transducteurs et la structure de chacun sont fixées à l'avance uniquement sur la base de et . Chaque passe (transducteur) préserve la régularité, il n'est donc pas nécessaire de les entrelacer en une seule passe. Oui, pas "élémentaire". Mais construire un FSA en une seule fois, avec un seul passage, serait terriblement complexe. M 1 , 0 a bM1 , 0uneb
David Lewis
1
@Raphael - oui, c'est très puissant. En fait, de nombreuses familles non régulières sont également fermées sous des transducteurs à états finis. Et, vous pouvez utiliser des transducteurs comme mécanismes de réduction, obtenant toute une théorie de la complexité "structurelle" des langages non réguliers.
David Lewis
8

Astuce n ° 1 : résolvez d'abord le problème le plus populaire "écrire un automate qui reconnaît les représentations décimales / binaires des nombres divisibles par 3" lorsque le bit le moins significatif apparaît en premier.

Question intermédiaire: prouver que est régulier.{ ¯ ax + bax + b 0x Z }{ ax + b¯¯¯¯¯¯¯¯¯¯¯¯¯¯ax + b 0x Z }

Astuce # 2 : Le graphique de la fonction "modulo " est fini. Vous pouvez le calculer pour chaque dans qui est à la fois l'ensemble des chiffres et la langue de votre automate.( n 10 n + d ) a d { 0 , , 9 }( n 10 n + d)une{ 0 , , 9 }

Astuce n ° 3 : maintenant, remplacez avec . Qu'est-ce que cela change? Essayez d'utiliser le fait que les langages réguliers sont stables par intersection au lieu de construire un automate ad-hoc .x Z x Nx Zx N

Astuce n ° 4 : supposons maintenant que un est un nombre premier ( de sorte que Z / un Z est un champ) et que nous sommes encore dans le cas où x Z . Nous utilisons maintenant une représentation où le premier bit est le bit le plus significatif . Pouvez-vous construire l'automate de la même manière?aZ/aZxZ

Astuce # 5 : vous n'avez pas toujours besoin de construire un automate pour prouver qu'un langage est régulier. Comment pouvez-vous utiliser les résultats précédents pour prouver que M est régulier? (avec le bit le plus significatif en premier)M

jmad
la source
N'hésitez pas à commenter si vous pensez que ce n'est pas approprié.
jmad
L'astuce # 1 est un grand pas. En allusion # 4, il est important de se rendre compte que un { 2 , 5 } et un 10 sont différents. Passer par Z ressemble à un détour, il faut gérer le caractère du signe: pourquoi ne pas rester en N ? a{2,5}a10ZN
Gilles 'SO- arrête d'être méchant'
@ Gilles: Je voulais dire ¯ a x + b quand a x + b 0 et x Z , car 3 x + 1234 est fastidieux à reconnaître. ax+b¯¯¯¯¯¯¯¯¯¯¯¯¯¯ax+b0xZ3x+1234
jmad
@ Gilles: Je pense que l'indice # 1 est trop cool pour être gâté. Vous avez probablement raison à propos de l'indice # 4.
jmad
5

Je suis l'idée de @vonbrand:

Astuce 1:

Résolvez d'abord pour b = 0 . Vous pourriez utiliser le théorème de Myhill-Nerode .b=0

Nous définissons la relation suivante . Il s'agit évidemment d'une relation d'équivalence. De plus, il est droite, car si nous ajoutons un chiffre nous obtenons . Enfin, il sature , puisque est la classe d'équivalence . Puisque a un nombre fini de classes, nous avons par le théorème de Myhill-Nerode qu'il est régulier. La FSA est associé est minime et a états.ˉ x ˉ y :x ymoda d ˉ xˉ yX¯y¯:x ymodune10 x + d 10 y + dmoduneˉ x d ˉ y dLL[0]aX¯y¯10 x + d10 y+ dmoduneX¯y¯LL[0]a

Astuce 2:

Résoudre le cas général, réutiliser l'automate induit par le cas .b = 0b=0

Nous savons que le langage est régulier pour . Il suffit donc de prendre état FSA pour la langue . Maintenant , nous construisons un FSA pour . Supposons que a chiffres. Ensuite, le FSA se ramifie comme un arbre à 10 aires de profondeur et contient tous les chemins vers des nombres avec chiffres. Tous les états qui peuvent être atteints avec un nombre qui n'est pas sous la forme rejettent autrement acceptent. Enfin on relie la partie arborescente du FSA à l'automate , selon le reste par la division par .b = 0 a M b = 0 L b k k k a x + b M ab=0aMb=0Lbkkkax+bMa

A.Schulz
la source
Je comprends la technique, mais pas les détails. L'astuce 1 ne concerne-t-elle pas également le cas a = 1 ? De plus, pour le mod 10, je m'attendrais à 10 états (pas a )? a=1a
Hendrik Jan
3

La langue est régulière.

Astuce: éliminer les neuf


Idée de preuve

Pour a = 9 et b < 9 ,a=9b<9

construire un automate avec 9 états étiquetés de 0 à 8 . 0 est l'état initial et le dernier état final est b . De l'état s , sur le chiffre d , transition vers l'état ( s + d )9080bsdm o d9 .(s+d)mod9

Pour gérer d'autres valeurs de a qui sont coprimes avec 10 ,a10

regrouper les chiffres en paquets pour trouver des k tels que a divise 10 k - 1 (par exemple, prendre k = 3 si a = 37 car 999 = 27 × 37 ).ka10k1k=3a=37999=27×37

Pour gérer les valeurs de a dont les seuls facteurs premiers sont 2 et 5 ,a25

notez qu'il s'agit d'un nombre fini de chiffres à la fin.

Pour généraliser à toutes les valeurs de a et b ,ab

utiliser le fait que l'union et l'intersection des langues régulières sont régulières, que les langues finies sont régulières et que les multiples de a 1a 2 sont exactement les multiples des deux quand a 1 et a 2 sont premiers.a1a2a1a2

Notez que nous utilisons la technique qui vous convient; les trois principales techniques élémentaires (expressions régulières, automates finis, propriétés de la théorie des ensembles) sont toutes représentées dans cette preuve.


Preuve détaillée

Soit a = 2 p 5 q a ' avec un ' premier avec 10 . Soit M = { ¯ a a=2p5qaa10x + bxZax + b 0 } et M = { ¯ 2 p 5 qM={ax+b¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯xZax+b0}x + bxZ2p5qx + b 0 } . Par arithmétique élémentaire, les nombres égaux à b modulo a sont exactement les nombres égaux à b modulo a et à b modulo 2 p 5 q , donc M { ¯ xx b } = M M { ¯ xx b } . Étant donné que l'intersection des langues régulières est régulière, etM′′={2p5qx+b¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯xZ2p5qx+b0}babab2p5qM{x¯¯¯xb}=MM′′{x¯¯¯xb}{ ¯ xx b } est régulier car c'est le complément d'un langage fini (donc régulier), si M et M sont également réguliers, alors M { ¯ xx b } est régulier; et M est donc régulier puisqu'il s'agit de l'union de cette langue avec un ensemble fini. Donc pour conclure la preuve il suffit de prouver que M et M sont réguliers.{x¯¯¯xb}MM′′M{x¯¯¯xb}MMM′′

Commençons par M , soit les nombres modulo 2 p 5 q . Les entiers dont l'expansion décimale est en M " sont caractérisés par leurs derniers m a x ( p , q ) chiffres, car changer les chiffres plus à gauche signifie ajouter un multiple de 10 m a x ( p , q ) qui est un multiple de 2 p 5 q . D'où 0 M = FM′′2p5qM′′max(p,q)10max(p,q)2p5q0M′′=F est l'alphabet de tous les chiffres et F est un ensemble fini de mots de longueur m a x ( p , q ) , et M = ( F ) ( ( { 0 } ) ) est un régulier Langue.Fmax(p,q)M′′=(F)(({0}))

Passons maintenant à M , c'est-à-dire les nombres modulo a a est coprime avec 10 . Si a = 1 alors M est l'ensemble des expansions décimales de tous les naturels, c'est-à-dire M = { 0 } ( ( { 0 } ) ) , qui est une langue régulière. Nous supposons maintenant un > 1 . Soit k = a -Maa10a=1MM={0}(({0}))a>11 . Par le petit théorème de Fermat, 10 a - 11k=a1moda , c'est-à-dire que a divise 10 k - 1 . Nous construisons un automate fini déterministe qui reconnaîtra 0 M comme suit:10a11modaa10k10M

  • Les états sont [ 0 , k - 1 ] × [ 0 , 10 k - 2 ] . La première partie représente une position numérique et la seconde partie représente un nombre modulo 10 k - 1 .[0,k1]×[0,10k2]
  • L'état initial est ( 0 , 0 ) .
  • Il y a une transition étiquetée d de ( i , u ) à ( j , v ) ssi v d 10 i + umod10 k - 1 et j i + 1modk .
  • Un état ( i , u ) est final si u bmoda (notez que a divise 10 k - 1 ).

L'état ( i , u ) atteint par un mot ¯ x satisfait i | ¯ x |modk et u xmod10 k - 1 . Cela peut être prouvé par induction sur le mot, en suivant les transitions sur l'automate; les transitions sont calculées pour cela, en utilisant le fait que 10 k1mod10 k - 1 . Ainsi l'automate reconnaît les expansions décimales (permettant les zéros initiaux) des nombres de la forme u + y 10 k avec u bmoda ; depuis 10 k1moda ' , l'automate reconnaît les expansions décimales des nombres égaux à b modulo a ' permettant des zéros initiaux, qui est 0 M ' . Cette langue s'est donc avérée régulière. Enfin, M = ( 0 M ) ( ( { 0 } ) ) est un langage régulier.

Pour généraliser aux bases autres que 10 , remplacer 2 et 5 ci-dessus par tous les facteurs premiers de la base.

Preuve formelle

À gauche comme exercice pour le lecteur, dans votre prouveur de théorème préféré.

Gilles 'SO- arrête d'être méchant'
la source