Automates

isoz3

Bonjour

Je suis tombé il y a quelques temps sur un document présentant trois automates.

1. Un automate qui savait reconnaître tous les nombres entiers ne commencant pas par zéro
2. Un automate qui savait reconnaître tous les multiples de 3
3. Un automate qui reconnaît une entrée numérique dans un tableur (par exemple : 12,3 ou 08 ou -15 ou 5E12 ou 14E-3)

J'aurais voulu associer ces automates à leur catégorie mais je ne suis pas sûr de la justesse de mon choix. Selon moi ce sont trois automates déterministes et finis travaillant sur un langage régulier.
Est-ce bien juste?
Merci d'avance pour votre aide

PS: si jamais je peux joindre un PDF avec un schéma de ces automates

nico8

salut,

c'est quoi ton alphabet ?

pour le 1) et le 2), l'idee c'est de ne regarder tes nombre modulo 3 et 10
apres l'automate depend fortement de la base de numeration que tu utilises
le plus simple serait de l'ecrire en binaire, et d'ajouter 2^i mod 3/10 pour chaque 1 de ton ecriture, comme ca prend un nombre fini de valeurs, ca boucle et ton automate sera donc fini

pour le 3) c'est beaucoup plus simple :
il suffit de reconnaitre un language de la forme {-;e} C* , C* E {-;e} C* , qui est bien regulier
ou e est le mot vide, C est l'alphabet {0;1;...;9} et C* l'ensemble des mots (ie des nombres) qu'on peut ecrire avec
tu peux eventuellement rajouter quelques subtilites si tu desires une ecriture particuliere

sinon, les automates finis non deterministes a n etats peuvent toujours etre reduits a un automate fini deterministe a 2^n etats ou moins (cette borne peut etre atteinte), et reconnaissent dans tous les cas un language regulier

j'espere avoir ete assez complet

isoz3

C'est parfait.

Merci!