Comprendre les machines d'état

Une introduction aux concepts de l'informatique

L'informatique nous permet de programmer, mais il est possible de faire beaucoup de programmation sans comprendre les concepts informatiques sous-jacents.

Ce n'est pas toujours une mauvaise chose. Lorsque nous programmons, nous travaillons à un niveau d'abstraction beaucoup plus élevé.

Lorsque nous conduisons une voiture, nous ne nous préoccupons que de deux ou trois pédales, d'un levier de vitesses et d'un volant. Vous pouvez conduire une voiture en toute sécurité sans avoir aucune idée précise de son fonctionnement.

Cependant, si vous voulez conduire une voiture à la limite de ses capacités, vous devez en savoir beaucoup plus sur les automobiles que les trois pédales, le levier de vitesses et le volant.

Il en va de même pour la programmation. Une grande partie du travail quotidien peut être accompli avec peu ou pas de compréhension de l'informatique. Vous n'avez pas besoin de comprendre la théorie computationnelle pour créer un formulaire «Contactez-nous» en PHP.

Cependant, si vous envisagez d'écrire du code qui nécessite un calcul sérieux, vous devrez en savoir un peu plus sur le fonctionnement du calcul sous le capot.

Le but de cet article est de fournir quelques informations de base pour le calcul. S'il y a un intérêt, je pourrais continuer avec des sujets plus avancés, mais pour le moment, je veux examiner la logique derrière l'un des dispositifs de calcul abstrait les plus simples - une machine à états finis .

Machines à états finis

Une machine à états finis est une abstraction mathématique utilisée pour concevoir des algorithmes.

En termes plus simples, une machine d'état lira une série d'entrées. Lorsqu'il lit une entrée, il passe à un état différent. Chaque état spécifie vers quel état basculer, pour une entrée donnée. Cela semble compliqué mais c'est vraiment assez simple.

Imaginez un appareil qui lit un long morceau de papier. Pour chaque pouce de papier, une seule lettre est imprimée dessus - soit la lettre «a» ou la lettre «b».

Au fur et à mesure que la machine d'état lit chaque lettre, elle change d'état. Voici une machine à états très simple:

Les cercles sont des « états » dans lesquels la machine peut se trouver. Les flèches sont les transitions . Donc, si vous êtes dans l'état s et que vous lisez un «a», vous passerez à l'état q . Si vous lisez un «b», vous resterez dans l'état s .

Donc, si nous commençons par s et lisons la bande de papier ci-dessus de gauche à droite, nous lirons le «a» et passerons à l'état q .

Ensuite, nous lirons «b» et reviendrons à l'état s .

Un autre «b» nous gardera sur s , suivi d'un «a» - qui nous ramène à l' état q . Assez simple, mais à quoi ça sert?

Eh bien, il s'avère que vous pouvez faire passer une bande dans la machine d'état et dire quelque chose sur la séquence de lettres, en examinant l'état dans lequel vous vous retrouvez.

Dans notre machine à états simple ci-dessus, si nous finissons par l'état s , la bande doit se terminer par une lettre «b». Si nous terminons par l'état q , la bande se termine par la lettre «a».

Cela peut sembler inutile, mais il y a énormément de problèmes qui peuvent être résolus avec ce type d'approche. Un exemple très simple serait de déterminer si une page HTML contient ces balises dans cet ordre:

La machine d'état peut passer à un état indiquant qu'elle a lu la balise html, faire une boucle jusqu'à ce qu'elle atteigne la balise head, boucler jusqu'à ce qu'elle atteigne la balise head close, etc.

S'il réussit à atteindre l'état final, vous avez ces balises particulières dans le bon ordre.

Les machines à états finis peuvent également être utilisées pour représenter de nombreux autres systèmes - tels que la mécanique d'un parcmètre, une machine à pop, une pompe à essence automatisée et toutes sortes d'autres choses.

Machines à états finis déterministes

Les machines à états que nous avons examinées jusqu'à présent sont toutes des machines à états déterministes . À partir de n'importe quel état, il n'y a qu'une seule transition pour toute entrée autorisée. En d'autres termes, il ne peut pas y avoir deux chemins menant hors d'un état lorsque vous lisez la lettre «a». Au début, cela semble idiot de faire même cette distinction.

À quoi sert un ensemble de décisions si la même entrée peut entraîner le passage à plus d'un état? Vous ne pouvez pas dire à un ordinateur, if x == truepuis exécuter doSomethingBigou exécuter doSomethingSmall, n'est-ce pas?

Eh bien, vous pouvez en quelque sorte avec une machine à états.

La sortie d'une machine d'état est son état final. Il effectue tout son traitement, puis l'état final est lu, puis une action est entreprise. Une machine d'état ne fait rien lorsqu'elle passe d'un état à l'autre.

Il traite, et quand il arrive à la fin, l'état est lu et quelque chose d'extérieur déclenche l'action souhaitée (par exemple, distribuer une canette de soda). C'est un concept important lorsqu'il s'agit de machines à états finis non déterministes .

Machines à états finis non déterministes

Les machines à états finis non déterministes sont des machines à états finis où une entrée donnée d'un état particulier peut conduire à plus d'un état différent.

Par exemple, disons que nous voulons construire une machine à états finis capable de reconnaître des chaînes de lettres qui:

  • Commencez par la lettre 'a'
  • et sont ensuite suivis par zéro ou plusieurs occurrences de la lettre 'b'
  • ou, zéro ou plusieurs occurrences de la lettre «c»
  • se terminent par la lettre suivante de l'alphabet.

Les chaînes valides seraient:

  • abbbbbbbbbc
  • abbbc
  • acccd
  • acccccd
  • ac (aucune occurrence de b)
  • ad (aucune occurrence de c)

Ainsi, il reconnaîtra la lettre «a» suivie de zéro ou plus de la même lettre de «b» ou «c», suivie de la lettre suivante de l'alphabet.

Une façon très simple de représenter cela est d'utiliser une machine à états qui ressemble à celle ci-dessous, où un état final de t signifie que la chaîne a été acceptée et correspond au modèle.

Voyez-vous le problème? Le point de départ de s , nous ne savons pas quel chemin prendre. Si nous lisons la lettre «a», nous ne savons pas s'il faut passer à l'état q ou r.

Il existe plusieurs façons de résoudre ce problème. La première consiste à revenir en arrière. Vous prenez simplement tous les chemins possibles et ignorez ou reculez de ceux où vous êtes coincé.

C'est essentiellement ainsi que fonctionnent la plupart des ordinateurs qui jouent aux échecs. Ils examinent toutes les possibilités - et toutes les possibilités de ces possibilités - et choisissent la voie qui leur donne le plus d'avantages par rapport à leur adversaire.

L'autre option est de convertir la machine non déterministe en une machine déterministe.

L'un des attributs intéressants d'une machine non déterministe est qu'il existe un algorithme pour transformer toute machine non déterministe en une machine déterministe. Cependant, c'est souvent beaucoup plus compliqué.

Heureusement pour nous, l'exemple ci-dessus n'est que légèrement plus compliqué. En fait, celle-ci est suffisamment simple pour que nous puissions la transformer en une machine déterministe dans notre tête, sans l'aide d'un algorithme formel.

La machine ci-dessous est une version déterministe de la machine non déterministe ci-dessus. Dans la machine ci-dessous, un état final de t ou v est atteint par toute chaîne acceptée par la machine.

Le modèle non déterministe comporte quatre états et six transitions. Le modèle déterministe a six états, dix transitions et deux états finaux possibles.

Ce n'est pas beaucoup plus, mais la complexité augmente généralement de manière exponentielle. Une machine non déterministe de taille moyenne peut produire une machine déterministe absolument énorme .

Expressions régulières

Si vous avez fait n'importe quel type de programmation, vous avez probablement rencontré des expressions régulières. Les expressions régulières et les machines à états finis sont fonctionnellement équivalentes. Tout ce que vous pouvez accepter ou associer avec une expression régulière peut être accepté ou mis en correspondance avec une machine à états.

Par exemple, le modèle décrit ci-dessus pourrait être mis en correspondance avec l'expression régulière: a(b*c|c*d)

Les expressions régulières et les machines à états finis ont également les mêmes limitations. En particulier, ils ne peuvent correspondre ou accepter que des modèles qui peuvent être traités avec une mémoire finie.

Alors, à quel type de motifs ne peuvent-ils pas correspondre? Supposons que vous souhaitiez uniquement faire correspondre les chaînes de 'a' et 'b', où il y a un nombre de 'a' suivi d'un nombre égal de 'b'. Ou n 'a suivis de n ' b, où n est un nombre.

Des exemples seraient:

  • un B
  • aabb
  • aaaaaabbbbbb
  • aaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb

Au début, cela semble être une tâche facile pour une machine à états finis. Le problème est que vous serez rapidement à court d'états, ou vous devrez supposer un nombre infini d'états - à quel point ce n'est plus une machine à états finis .

Disons que vous créez une machine à états finis qui peut accepter jusqu'à 20 'a's suivis de 20' b's. Cela fonctionne bien, jusqu'à ce que vous obteniez une chaîne de 21 'a's suivis de 21' b's - à quel point vous devrez réécrire votre machine pour gérer une chaîne plus longue.

Pour toute chaîne que vous pouvez reconnaître, il y en a une un peu plus longue que votre machine ne peut pas reconnaître car elle manque de mémoire.

Ceci est connu sous le nom de lemme de pompage qui dit essentiellement: «si votre motif a une section qui peut être répétée (comme celle ci-dessus), alors le motif n'est pas régulier».

En d' autres termes, ni une expression régulière , ni une machine à états finis peuvent être construits qui reconnaîtra toutes les chaînes qui ne correspondent au modèle.

Si vous regardez attentivement, vous remarquerez que ce type de motif où chaque «a» a un «b» correspondant, ressemble beaucoup au HTML. Dans n'importe quelle paire de balises, vous pouvez avoir n'importe quel nombre d'autres paires de balises correspondantes.

Ainsi, bien que vous puissiez utiliser une expression régulière ou une machine à états finis pour reconnaître si une page HTML a le ; et les éléments dans le bon ordre, vous ne pouvez pas utiliser une expression régulière pour dire si une page HTML entière est valide ou non - car HTML n'est pas un modèle régulier.ml>, ead>

Machines de Turing

Alors, comment reconnaissez -vous les modèles non réguliers ?

Il existe un dispositif théorique similaire à une machine à états, appelé une machine de Turing. Elle est similaire à une machine à états finis en ce qu'elle a une bande de papier qu'elle lit. Mais, une machine de Turing peut effacer et écrire sur la bande de papier.

Expliquer une machine de Turing prendra plus d'espace que nous avons ici, mais il y a quelques points importants pertinents pour notre discussion sur les machines à états finis et les expressions régulières.

Les machines de Turing sont complètes en termes de calcul - ce qui signifie que tout ce qui peut être calculé peut être calculé sur une machine de Turing.

Puisqu'une machine de Turing peut écrire aussi bien que lire à partir de la bande de papier, elle n'est pas limitée à un nombre fini d'états. La bande de papier peut être supposée avoir une longueur infinie. Bien sûr, les ordinateurs réels n'ont pas une quantité infinie de mémoire. Mais, ils contiennent généralement suffisamment de mémoire pour que vous n'atteigniez pas la limite du type de problèmes qu'ils traitent.

Les machines de Turing nous offrent un dispositif mécanique imaginaire qui nous permet de visualiser et de comprendre le fonctionnement du processus de calcul. Il est particulièrement utile pour comprendre les limites du calcul. S'il y a de l'intérêt, je ferai un autre article sur les machines de Turing dans le futur.

Pourquoi est-ce important?

Alors, à quoi ça sert? Comment cela va vous aider à créer ce prochain formulaire PHP?

Indépendamment de leurs limites, les machines à états sont un concept très central de l'informatique. En particulier, il est significatif que pour toute machine à états non déterministe que vous pouvez concevoir, il existe une machine à états déterministe qui fait la même chose.

C'est un point clé, car cela signifie que vous pouvez concevoir votre algorithme de la manière la plus simple à envisager. Une fois que vous avez un algorithme fonctionnel, vous pouvez le convertir sous la forme la plus efficace.

Le fait de comprendre que les machines à états finis et les expressions régulières sont fonctionnellement équivalentes ouvre des utilisations incroyablement intéressantes pour les moteurs d'expressions régulières, en particulier lorsqu'il s'agit de créer des règles métier pouvant être modifiées sans recompiler un système.

Une base en informatique vous permet de prendre un problème que vous ne savez pas résoudre et de raisonner: «Je ne sais pas comment résoudre X, mais je sais comment résoudre Y. Et je sais comment convertir une solution pour Y en une solution pour X. Par conséquent, je sais maintenant comment résoudre X. »

Si vous aimez cet article, vous apprécierez peut-être ma chaîne YouTube où je crée occasionnellement une vidéo ou un dessin animé sur certains aspects de la création de logiciels. J'ai aussi une liste de diffusion pour les personnes qui aimeraient recevoir un courriel occasionnel lorsque je produis quelque chose de nouveau.

Publié à l'origine sur blog.markshead.com le 11 février 2018.