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
* * Présentation :* * Un automate fini déterministe ( DFA\ * ) est essentiellement un " programme " qui lit une chaîne ( une collection ordonnée de caractères , membres d' un " alphabet " ) . Le programme maintient un état et garde une trace de l'endroit où il se trouve actuellement dans la chaîne pendant la lecture. La machine définit, pour chaque état, à quel état elle va ensuite pour un caractère donné (c'est pourquoi elle est *déterministe* - elle doit spécifier *exactement* une destination pour chaque combinaison d'état et de caractère). La machine " accepte " ou " rejette " une chaîne , selon l' état dans lequel elle se trouve à la fin de la lecture . * * Exemple :* * Ainsi, par exemple, disons que nous avons un alphabet composé uniquement de « a » et « b », et que nous avons un DFA avec deux états, « s0 » et « s1 ». Définissons la fonction comme suit : * Lorsque la machine est dans l'état « s0 » et lit « a », restez dans « s0 ». * Lorsque la machine est dans l'état « s0 » et lit « b », passez à « s1 ». * Lorsque la machine est dans l'état « s1 » et lit « a », restez dans « s1 ». * Lorsque la machine est dans l'état « s1 » et lit « b », passez à « s0 ». Ainsi , lorsque la machine lit une chaîne , disons abbab Il part de " s0 " ( par défaut ) et vérifie le premier caractère , " a " . Selon nos règles , il reste où il est et passe au caractère suivant , " b " . Maintenant , nos règles indiquent que l' état actuel devient " s1 " , et non " s0 " . Notre machine lit à nouveau dans " b " , et puisque nous sommes dans " s1 " , nous revenons à " s0 " . Et ainsi de suite jusqu'à la fin de la chaîne. Dans notre cas , nous nous retrouvons en " s1 " . Enfin , nous avons besoin de notre machine pour nous dire quelque chose de valable ; nous devons dire dans lequel de nos états nous voulons nous retrouver. Si une chaîne se retrouve dans l'un de nos états « finaux », nous disons que la machine « accepte » la chaîne. Il peut y avoir plusieurs états " finaux " . Dans notre exemple, disons que notre état final est « s0 ». Ensuite , nous accepterons toute chaîne avec * un nombre pair de la lettre b apparaissant dans la chaîne * . Alors , qu'est - ce que cela a à voir avec les expressions régulières ? Eh bien, les expressions régulières peuvent être considérées comme une manière abrégée de définir un DFA. Les expressions régulières acceptent également les chaînes et déterminent si elles « correspondent » ou non. Notre exemple peut être écrit dans l' expression régulière suivante : a * ( b ( a * ) b ( a * ) ) * Ce qui signifie que n'importe quel nombre de " a " peut apparaître n'importe où dans la chaîne , mais s'il y a un " b " , un autre " b " doit apparaître plus tard . Vous pouvez également le définir plus en détail en utilisant ce qui suit : M = notre machine = ( Q , Σ , δ , q0 , F ) Q = notre ensemble d'états = { s0 , s1 } Σ = notre alphabet = { a , b } δ = notre fonction de transition (voir ci-dessus) q0 = l'état de départ = s0 F = l'ensemble des états finaux = {s0} minutes s'écoulant aujourd'hui , alors j'espère avoir raison . \ * À ne pas confondre avec Stephen Colbert , qui a un doctorat en beaux - arts . Son comportement est très peu déterministe.