Automates et langages formels III – L’automate minimal (a)

J’ai annoncé dans cet article deux constructions générales d’automates acceptant un langage donné.

La première est explicitée dans le billet en question. Elle est assez banale. Suivant immédiatement la définition de la notion d’automate, elle nous a permis cependant de vérifier très facilement qu’un langage est toujours accepté par un automate.

Nous allons étudier ici la seconde. Elle est nettement plus subtile et, pour la présenter, il est commode d’introduire de nouvelles notations.

Les ensembles U\cdot L et U^{-1}\cdot V

Considérons un alphabet A et une action à droite(*) \delta^* de A^* sur un ensemble Q. Ce dernier pourrait être A^* soi-même et \delta^* la concaténation, exemple qui sera utilisé de façon récurrente et sans être nécessairement explicitement annoncé.

Si U et V sont des sous-ensembles de Q et si L en est un de A^*, on pose(**)

U\cdot L=\{q\cdot m| q\in U, m\in L\}

et

U^{-1}\cdot V =\{m\in A^*| U\cdot m\cap V\neq\varnothing\}

Le premier ensemble est un ensemble d’éléments de Q, ceux en lesquels les mots appartenant à L transforment les éléments de U. Cette construction généralise la concaténation des langages à laquelle elle correspond lorsque Q est l’ensemble des mots sur A et \delta^* est la concaténation.

Le second est un ensemble de mots, ceux qui transforment un élément de U en un élément de V. Si, par exemple, \delta^* est l’action d’un automate déterministe dont s et F sont respectivement l’état initial et l’ensemble des états finals, alors s^{-1}\cdot F est le langage accepté par l’automate, par définition de ce dernier.

La propriété suivante est bien utile. Elle n’est pas difficile à prouver — il s’agit simplement d’appliquer les définitions. Je ne le ferai pas car c’est peut-être une bonne chose à faire soi-même pour assimiler celles-ci.

(1) (U\cdot L)^{-1}\cdot V=L^{-1}\cdot(U^{-1}\cdot V)

J’attire votre attention sur le fait que, dans le membre de droite, deux actions entrent en jeu. Il y a \delta^* (pour le « . » le plus à droite) et il y a la concaténation des mots. Le membre de gauche est plus homogène : les deux « . » sont relatifs à \delta^*.

L’automate minimal d’un langage

L’ensemble des états de l’automate minimal \mathcal A(L)=(Q(L),A,s_L,F(L),\delta^*_L) d’un langage L\subset A^* est

Q(L)=\{m^{-1}\cdot L|m\in A^*\}

Son état initial est s_L=\varepsilon^{-1}\cdot L = L et un état q=m^{-1}\cdot L est final si \varepsilon\in q, ce qui équivaut à m\in L. D’après (1), l’application

\delta^*_L: (q,m)\in Q(L)\times A^*\mapsto m^{-1}\cdot q\in Q(L)

est une action à droite. Elle complète notre définition de l’automate minimal de L.

A chaque état q de l’automate correspond le langage

s^{-1}\cdot q = \{m\in A^*|q=m^{-1}\cdot L\}

formés des mots qui transforment s en q. Ces langages partitionnent A^*. De plus, si a est une lettre,

s^{-1}\cdot (q\cdot a)=(s^{-1}\cdot q)a

Dans certains cas, il est facile de déterminer directement les langages s^{-1}\cdot q et cette formule permet alors de construire aisément la fonction de transition de l’automate.

On va illustrer cela sur deux exemples que nous avons rencontrés dans le billet précédent.

Construisons d’abord l’automate minimal du langage a^*b^* sur l’alphabet \{a,b\}. Dans la table suivante, ses états sont décrits dans la colonne centrale, leurs statuts figurent dans la colonnes de droite et les langages associés, dans celle de gauche(***). On l’obtient sans difficulté.

\begin{array}{c|c|c} m\in& m^{-1}\cdot L&\mathrm{statut}\\ \hline  \hline a^*&L&\mathrm{initial,final}\\ \hline a^*b^*b&b^*&\mathrm{final}\\ \hline \mathrm{autre}&\varnothing&\mathrm{non\ final}\\ \hline\end{array}

La table de la fonction de transition s’en déduit immédiatement :

\begin{array}{c||c|c} \delta & a & b \\ \hline\hline L & L & b^* \\ \hline b^* & \varnothing & b^* \\ \hline \varnothing & \varnothing & \varnothing\end{array}

et nous trouvons ainsi l’automate

Comme second exemple, nous allons déterminer l’automate minimal du langage

L=\{a^nb^n|n\in \mathbb N\}

sur le même alphabet. La table des états est à peine plus difficile à obtenir. La voici

\begin{array}{c|c|c} m\in& m^{-1}\cdot L&\mathrm{statut}\\ \hline\hline\varepsilon &L&\mathrm{initial,final}\\ \hline  a^k (k>0) & Lb^k & \mathrm{non\ final} \\ \hline \{a^\ell b^{\ell-k}|\ell >k\} (k>0) & b^k & \mathrm{non\ final} \\ \hline L & \varepsilon & \mathrm{final}\\ \hline \mathrm{autre} & \varnothing &  \mathrm{non\ final} \\ \hline  \end{array}

Comme d’habitude, les accolades manquent lorsque le langage ne contient qu’un élément. Il y a cette fois une infinité d’états, décrits dans les deux lignes où apparait le paramètre k.

Je ne détaillerai pas la table de la fonction de transition qu’on en déduit facilement. Je vous laisserai donc le soin de vérifier qu’on obtient l’automate suivant

automate_ex_1

Il présente deux rangées « horizontales » d’états. Les états non finals de la rangée inférieure sont ceux décrits dans la deuxième ligne de la table ci-dessus tandis que ceux de l’autre rangée apparaissent dans sa troisième ligne.

A suivre …

Comme je l’ai laissé entendre, le langage accepté par l’automate minimal d’un langage L est L lui-même. C’est évident puisque, par construction,

s_L\cdot m = m^{-1}\cdot L

et m^{-1}\cdot L est final si, et seulement si, m appartient à L.

Il reste à expliquer en quoi \mathcal{A}(L) est « minimal » et à en donner quelques propriétés, ce que je ferai ailleurs pour conserver à ce billet une taille raisonnable.

__________
(*) Pour rappel,

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

vérifie l’identité q\cdot (mm')=(q\cdot m)\cdot m' ainsi que q\cdot \varepsilon = q
(**) Pour simplifier les notation, lorsque U,V ou L ne contient qu’un seul élément, x, on substitue celui-ci à \{x\} dans les notations introduites. Par exemple, si m est un mot, U\cdot m est mis pour U\cdot \{m\}
(***) « autre » est mis pour l’ensemble des mots n’appartenant pas à un des langages déjà considérés.

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