Langage des valeurs d'une fonction affine

É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:$\bar n$$n$0$a$$b$$a > 0$$a$

est-il régulier? sans contexte?$M$

(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.}

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 > $a$$a - 1$$q$$d$$(10 q + d) \bmod a$$b \bmod a$$b > a$

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 obtient$M_{a,b}$

$M_{1,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\}$

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 ˉ $a$$M_{a,0}$$M_{1,0}$$\bar x \rightarrow \overline {ax}$$M_{a,0}$$x$$\bar a$

ˉ x → ¯ 2 x ˉ x → ˉ x$\bar x \rightarrow \overline {2x}$ qui est$\bar x \rightarrow \bar x0$

et

$\bar x \rightarrow \overline {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é.$\bar x$

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 $M_{a,b}$$M_{a,0}$$b$$T_b$

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$d$$S_d$$d$

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.

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.$\{ \overline{a\,x+b}\mid a\,x+b≥0 \quad x\in\mathbb{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 \mapsto 10n+d)$$a$$d$$\{0, \dots, 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 ∈ $x∈\mathbb Z$$x∈\mathbb 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?$a$$\mathbb Z/a\mathbb Z$$x∈\mathbb Z$

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$

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 ≈ ˉ $\bar x\approx \bar y :\iff x\equiv y \mod a$$d$⟺10 x + d ≡ 10 y + dmodune⟺ˉ x d≈ ˉ y dLL[0]≈$\bar x \approx \bar y \iff 10x+d \equiv 10y+d \mod a \iff \bar x d \approx \bar y d$$L$$L$$[0]$$\approx$$a$

Astuce 2:

Résoudre le cas général, réutiliser l'automate induit par le cas .$b=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 $b=0$$a$$M$$b=0$$L$$b$$k$$k$$k$$ax+b$$M$$a$

La langue est régulière.

Astuce: éliminer les neuf

Idée de preuve

Pour a = 9 et b < 9 ,$a=9$$b < 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 $9$$0$$8$$0$$b$$s$$d$m o d9 .$(s + d) \;\mathrm{mod}\; 9$

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

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 ).$k$$a$$10^k-1$$k=3$$a=37$$999 = 27 \times 37$

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

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

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

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 1 ⋅ a 2 sont exactement les multiples des deux quand a 1 et a 2 sont premiers.$a_1 \cdot a_2$$a_1$$a_2$

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 = 2^p 5^q a'$$a'$$10$x + b ∣x∈Z∧a′x + b ≥ 0 } et M ″ = { ¯ 2 p 5 $M' = \{\overline{a'\,x+b} \mid x\in\mathbb{Z} \wedge a'\,x+b \ge 0\}$x + b ∣x∈Z∧2p5qx + 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 ∩ { ¯ x ∣ x ≥ b } = M ′ ∩ M ″ ∩ { ¯ x ∣ x ≥ b } . Étant donné que l'intersection des langues régulières est régulière, et$M'' = \{\overline{2^p 5^q\,x+b} \mid x\in\mathbb{Z} \wedge 2^p 5^q\,x+b \ge 0\}$$b$$a$$b$$a'$$b$$2^p5^q$$M \cap \{\overline{x} \mid x \ge b\} = M' \cap M'' \cap \{\overline{x} \mid x \ge b\}${ ¯ x ∣ x ≥ 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 ∩ { ¯ x ∣ x ≥ 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.$\{\overline{x} \mid x \ge b\}$$M'$$M''$$M \cap \{\overline{x} \mid x \ge b\}$$M$$M'$$M''$

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 ″ = ℵ ∗ F où$M''$$2^p 5^q$$M''$$\mathrm{max}(p,q)$$10^{\mathrm{max}(p,q)}$$2^p 5^q$$0^* M'' = \aleph^* 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.$\aleph$$F$$\mathrm{max}(p,q)$$M'' = (\aleph^* F) \cap ((\aleph \setminus \{0\}) \aleph^*)$

Passons maintenant à M ′ , c'est-à-dire les nombres modulo a ′ où 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 ′$M'$$a'$$a'$$10$$a' = 1$$M'$$M' = \{0\} \cup ((\aleph \setminus \{0\}) \aleph^*)$$a' > 1$1 . Par le petit théorème de Fermat, 10 a ′ - 1 ≡ $k = a'-1$moda ′ , c'est-à-dire que a ′ divise 10 k - 1 . Nous construisons un automate fini déterministe qui reconnaîtra 0 ∗ M ′ comme suit:$10^{a'-1} \equiv 1 \mod a'$$a'$$10^k-1$$0^* M'$

• 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,k-1] \times [0,10^k-2]$$10^k-1$
• L'état initial est ( 0 , 0 ) .$(0,0)$
• Il y a une transition étiquetée d de ( i , u ) à ( j , v ) ssi v ≡ d 10 i + $d$$(i,u)$$(j,v)$mod10 k - 1 et j ≡ i + $v \equiv d 10^i + u \mod 10^k-1$modk .$j \equiv i + 1 \mod k$
• Un état ( i , u ) est final si u ≡ $(i,u)$moda ′ (notez que a ′ divise 10 k - 1 ).$u \equiv b \mod a'$$a'$$10^k-1$

L'état ( i , u ) atteint par un mot ¯ x satisfait i ≡ | ¯ x$(i,u)$$\overline{x}$modk et u ≡ $i \equiv |\overline{x}| \mod k$mod10 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 k ≡ $u \equiv x \mod 10^k-1$mod10 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 ≡ $10^k \equiv 1 \mod 10^k-1$$u + y 10^k$moda ′ ; depuis 10 k ≡ $u \equiv b \mod a'$moda ' , 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.$10^k \equiv 1 \mod a'$$b$$a'$$0^* M'$$M' = (0^* M') \cap ((\aleph \setminus \{0\}) \aleph^*)$

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

Preuve formelle

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