Automates et langages formels II

De façon imagée, un automate est une machine présentant divers modes de fonctionnement. Une radio-lecteur de cd soit « est à l’arrêt » soit « fonctionne » et, dans ce cas, elle peut être soit en mode « radio » soit en mode « lecteur de cd » ; le mode radio se subdivise éventuellement en « ondes moyennes » , « longues ondes » ou « fréquence modulée » et, s’il y a des présélections possibles, elles définissent autant de modes de fonctionnement, etc. Une montre bracelet digitale pourrait être en mode « affichage de l’heure », « affichage de la date » ou en mode « réglages », …

On passe d’un mode à un autre par un petit nombre de commandes : en appuyant sur un bouton, en tournant une molette crantée, etc. ou par une séquence de commandes. Si les commandes sont symbolisées chacune par une lettre, les séquences en question sont représentées par des mots sur l’alphabet formé par ces lettres. Certaines séquences sont sans effet ou conduisent à une erreur. Les autres placent l’appareil dans les modes corrects de fonctionnement. Elles forment un langage sur l’alphabet en question. Il représente l’ensemble des manipulations licites de la machine.

Si on oublie la signification particulière des modes et des lettres, cette façon de voir les choses donne une idée intuitive raisonnable de ce qu’est un automate et de la manière générale dont il peut être utilisé pour définir un langage mais, alors que cette image repose sur des considérations concrètes, la définition formelle est très abstraite. Elle présente par contre l’avantage de faciliter le développement de la théorie.

Dans ce qui suit, je vais essayer de maintenir un certain équilibre entre les aspects intuitifs et les considérations plus formelles.

Automates déterministes

Un automate déterministe d’alphabet A est un ensemble Q sur lequel le monoïde A^* opère à droite et dans lequel on a choisi un élément s et une partie F. On le désigne si nécessaire par la notation

\mathcal A = (Q,A,s,F,\delta^*)

dans laquelle \delta^* dénote l’action à droite de A^* sur Q. Pour rappel, il s’agit d’une application

\delta^* :(q,m)\in Q\times A^*\mapsto q\cdot m\in Q

vérifiant(*)

(1) \forall q\in Q, \forall m,n\in A^* : \quad (q\cdot m)\cdot n=q\cdot (mn) \quad \& \quad q\cdot\varepsilon=q

Les éléments de Q sont les états de l’automate. L’état s est son état initial et les éléments de F en sont les états finals.

Dans l’image intuitive donnée plus haut d’une machine présentant plusieurs modes de fonctionnement, ceux-ci sont les états finals de la machine. Une image étant généralement imparfaite, il n’y a pas vraiment d’états non finals dans le modèle sommairement décrit ci-dessus, sinon des états imperceptibles à l’utilisateur dans lesquels la machine peut se trouver entre les commandes menant d’un mode à l’autre. Quant à l’état initial, il est relativement arbitraire mais on peut imaginer que c’est celui du repos, c’est-à-dire de la machine « éteinte ». Naturellement, un mot représente une séquence de commandes et son action sur un état donné est le mode résultant de l’application de ces commandes lorsque la machine se trouve dans cet état.

Le langage accepté par l’automate \mathcal A est l’ensemble des mots qui font passer de l’état initial à un état final, i.e.

L_\mathcal A :=\{m\in A^*|s.m\in F\}

On dit aussi de ces mots qu’ils sont acceptés par l’automate.

Représentation sagitale

A cause de la propriété (1), pour tout mot m=a_1\cdots a_k\in A^k et tout état q, on a

(2) q.m=(\cdots ((q\cdot a_1)\cdot a_2)\cdots)\cdot a_k

La donnée de l’action \delta^* équivaut donc à celle de l’action des lettres de l’alphabet A :

\delta : (q,a)\in Q\times A\mapsto q\cdot a \in Q

Cette fonction, appelée fonction de transition de l’automate, est souvent représentée par un graphe(**) avec lequel on confond d’habitude l’automate. Les sommets du graphe représentent les états de l’automate. De chacun d’eux partent autant d’arcs qu’il y a de lettres dans l’alphabet : il y a un arc joignant q à q', d’étiquette a\in A, si, et seulement si, q\cdot a=q'. Une pointe de flèche désigne l’état initial et les états finals sont représentés d’une manière particulière. En ce qui nous concerne, un état quelconque sera représenté par un cercle, dessiné en traits doubles pour un état final.

On interprète (2) en disant que le mot m décrit un chemin du graphe d’origine q. C’est le chemin passant successivement par les états q, q\cdot a_1, q\cdot a_1a_2,\ldots C’est encore le chemin issu de q et dont les arcs successifs ont pour étiquettes les lettres de m, lues de gauche à droite. Un mot est alors accepté par l’automate si, et seulement si, le chemin qu’il décrit à partir de l’état initial s’achève en un état final.

Voici un premier exemple.

Il s’agit d’un automate sur l’alphabet \{a,b\}. Il comporte trois états dont deux finals. L’état sur lequel il y a une boucle d’étiquette a,b est particulier(***) : il est non final et on ne le quitte plus quoi qu’on lise comme lettre une fois qu’on l’a atteint — on dit parfois que c’est un puits. Comme il n’est pas final, les mots qui y aboutissent ne sont pas acceptés par l’automate.

Le langage accepté par cet automate est

a^*b^*=\{a^pb^q|p,q\in \mathbb N\}

C’est l’ensemble des mots ne comportant pas de segment ba.

Il est clair que les mots de la forme a^pb^q sont acceptés par l’automate. Pour la réciproque, il suffit de noter que si on lit un a immédiatement après avoir lu un b, on tombe dans le puits si on n’y est pas déjà. Les mot acceptés par l’automate ne peuvent donc pas posséder de segment ba : ils appartiennent à a^*b^*.

L’automate représenté par

automate_ex_1

est construit sur le même alphabet que le précédent. Il possède une infinité d’états. Deux sont finals et il possède un puits. Il accepte le langage \{a^nb^n|n\in \mathbb N\}, ce qui n’est pas trop difficile à vérifier.

D’autres exemples ont été présentés dans cet article. Comme le premier, il s’agit d’automates finis déterministes, c’est-à-dire dont l’ensemble des états est fini, à la différence de l’automate précédent.

Il était inévitable que ce dernier possède une infinité d’états car c’est a priori le cas de tout automate acceptant le langage \{a^nb^n|n\in \mathbb N\}. En effet, pour un tel automate, les états

s, s\cdot a, s\cdot a^2, s\cdot a^3, \ldots, s\cdot a^n, \ldots

sont deux à deux distincts. De fait, supposons que s\cdot a^m=s\cdot a^n. Les états s\cdot a^mb^n et s\cdot a^nb^n sont alors égaux eux aussi. Or le second est final car le mot a^nb^n est accepté par l’automate. Dès lors le mot a^mb^n l’est également, ce qui exige m = n.

Un dernier exemple

Il se fait que tout les langages sont acceptés par des automates déterministes et il y a au moins deux constructions générales d’automates acceptant un langage L\subset A^* donné.

La première est relativement triviale et ne sert véritablement qu’à vérifier de façon rapide que L est accepté par un automate. Elle consiste à prendre pour états tous les mots sur l’alphabet A et à agir dessus par concaténation à droite. Le mot vide est choisi comme état initial tandis que les mots du langage L à reconnaître sont les états finals. Lorsque A comporte n lettres, cet automate est représenté par un arbre n-aire. La racine représente le mot vide, les sommets du premier niveau représentent les mots de longueur 1, etc.

Voici les premiers niveaux de l’arbre représentant l’automate associé à \{a^nb^n|n\in\mathbb N\}. Les états finals sont comme ci-dessus, marqués par des cercles en traits doubles. Il y en a un par niveau de rang pair, ce qui fait que je n’ai pas su en dessiner beaucoup.

automate_ex_3

La banalité de la construction réside dans le fait qu’il y a un état par mot et que les mots du langage sont exhaustivement marqués comme états finals. Autrement dit, l’automate est construit sans tenir compte le moins du monde de la structure du langage L.

Il en va tout autrement de la seconde construction mentionnée plus haut. Celle-ci débouche sur ce qu’on appelle l’automate minimal du langage, notion bien utile sur laquelle je reviendrai à une autre occasion.

Cela dit, il est amusant d’essayer de simplifier l’arbre ci-dessus. Par exemple, le sous-arbre de droite, qui ne contient aucun état final, pourrait être supprimé et sa racine remplacée par un puits. Pour la même raison, tous les descendants des états finals de niveau 2,4,6, … peuvent aussi être supprimés et les états en question directement branchés sur le puits. Cela fait, on peut tous les confondre avec l’un d’eux, par exemple celui de niveau 2, à condition de rediriger vers celui-ci les arcs aboutissants sur les autres. Cela ne changerait rien au langage accepté. En continuant de la sorte, en s’y prenant bien, on aboutirait au deuxième exemple d’automate présenté plus haut. Celui-ci n’est pas « améliorable » car il est minimal. Nous ne pouvons pas le voir à ce stade, mais je le précise pour faire un peu sentir ce que recouvre la minimalité.

Puisque tout langage est accepté par des automates, on ne peut guère espérer obtenir de résultats intéressants sans imposer à ceux-ci certaines propriétés. Une des plus importantes entre toutes est le caractère fini de l’automate. Nous verrons l’influence de cette hypothèse sur la famille des langages acceptés par ces automates.
__________
(*) Pour rappel, mn désigne la concaténation des mots m,n et \varepsilon est le mot vide.
(**) Un multigraphe orienté, plus précisément.
(***) Lorsque plusieurs arcs ont mêmes origine et extrémité, ils sont représentés par un seul arc mais affecté de toutes leurs étiquettes, séparées par des virgules. Ce genre de raccourci, fort commode, est très souvent utilisé — il le sera dans mes billets.

Publicités

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s