human
Automate déterministe à états finis Pas vraiment sûr de ce que cela signifie. Je viens également d'apprendre ce qu'est une expression régulière de wikipedia au cours des 15 dernières minutes. MERCI Expliquez comme si j'avais cinq ans.
gpt
Je vais donner à peu près l'explication de base que j'ai eue dans mon cours de théorie de l'automatisation. Tous les exemples seront basés sur [ cette image ] ( URL_0 ) . C'est une machine (théorique) qui lit à partir d'une bande de papier (en théorie) infinie. La machine fait les choses en fonction de ce que dit cette bande. En suivant les repères de la bande , la machine passe d' un état à l' autre , c'est à dire que lorsque vous démarrez , vous êtes à l' état 0 , en lisant la bande vous pouvez soit passer à l' état 1 ( lire " 1 " ) soit rester à l' état 0 ( lire " 0 " ) . Après avoir lu un marquage sur la bande, le lecteur avance d'un pas. Il est déterministe parce qu'il fera toujours la même chose pour la même bande -- à partir de l' état 0 , il ne se déplacera jamais nulle part en lisant un 0 , et il ne fera jamais rien d' autre que passer à l' état 1 en lisant un 1 . Un automate non déterministe peut faire plusieurs choses après avoir lu le même marquage sur la bande. Les automates non déterministes ne sont pas si grands, mais peuvent être transformés en automates déterministes sans en changer la fonction. Ils utilisent également - naturellement - très peu d'états lorsqu'ils sont optimisés. C'est fini parce que, eh bien, il y a un nombre fini d'états. Il existe théoriquement des automates à états infinis, mais naturellement ils sont un peu difficiles à fabriquer. Autre que ce qu'il est mécaniquement, c'est une représentation d'un type d'algorithme, basé sur la machine de Turing (chose merveilleuse, très amusante) mais pas aussi puissant. Edit : J'ai foiré les numéros d'état. Edit 2 : Mal lu la machine ( ou plutôt , l' explication de Wikipedias pour cela ) .. Edit 3 : Okay . La machine dans l'exemple accepte : * Aucune entrée ( epsilon ) * N'importe quel nombre de " 0 " * Deux un , avec n'importe quel nombre de " 0 " avant et après * 1 0 , n'importe quel nombre de " 1 " , 0 1 Ou pour le rendre plus succinct , eU0¤U(11)¤U(101¤01)¤ ( où e est epsilon , U est union et ¤ est une étoile de Kleene ) . Je pense que c'est vrai, cela fait un moment que je n'ai pas fait ce genre de choses.