Automates et langages formels IV – L’automate minimal (b) et le théorème de Kleene (a)

Nous poursuivons ici l’étude de l’automate minimal entamée dans le billet précédent. Nous allons voir en quoi cet automate est minimal. Ce sera l’occasion d’établir une propriété importante des langages acceptés par des automates finis. Ensuite, nous donnerons un critère de minimalité que nous appliquerons ultérieurement aux automates associés aux caractères de divisibilité dont nous avons parlé ici.

Nous utiliserons librement les notations des deux billets précédents.

Accessibilité

Un automate est accessible si tous ses états le sont, un état q étant accessible s’il est dans l’orbite de l’état initial c’est-à-dire s’il existe un mot m tel que q=s\cdot m soit encore si s^{-1}\cdot q\neq\varnothing.

Tant qu’on ne s’intéresse qu’aux mots acceptés par un automate, seuls ses états accessibles sont utiles et on peut supprimer les autres ainsi que les arcs dont ils sont une des extrémités : cela nous laisse avec un automate accessible acceptant le même langage.

L’automate minimal d’un langage L est accessible. En effet, ses états sont les ensembles de la forme m^{-1}\cdot L et, par définition de l’action, m^{-1}\cdot L =s_L\cdot m

La propriété suivante explique en quoi un automate minimal est, précisément, minimal.

(1) Soient un automate accessible \mathcal A = (Q,A,s,F,\delta^*) et L le langage qu’il accepte. Il existe une seule application \varphi : Q\mapsto Q(L) telle que

\varphi(s)=s_L \quad \& \quad \forall m\in A^* , \forall q\in Q : \quad \varphi(q\cdot m)=\varphi(q)\cdot m

Elle est surjective. De plus, un état q\in Q est final si, et seulement si, \varphi(q) est final.

Du fait de la surjectivité de \varphi, Q contient « au moins autant » d’éléments que Q(L). C’est tout à fait vrai lorsque ce dernier est fini; c’est à prendre comme une définition s’il est infini. En tout cas, il s’avère ainsi que de tous les automates accessibles acceptant un langage donné, son automate minimal compte un minimum d’états — d’où son nom.

Nous allons à présent démontrer (1). Ce n’est pas très difficile à faire, à condition cependant d’avoir bien à l’esprit la définition de l’automate minimal d’un langage. Comme elle est relativement abstraite, il serait peut-être utile de jeter un coup d’oeil au billet précédent où elle est présentée.

Donnons nous un langage L\subset A^* et un automate accessible \mathcal A = (Q,A,s,F,\delta^*) acceptant L. La preuve repose sur l’observation suivante :

Si q=s\cdot m, alors m^{-1}\cdot L=q^{-1}\cdot F.

Elle est facile à établir, ce que je ne ferai pas.

Cela étant, soit un état q de \mathcal A. Ce dernier étant accessible, il y a un mot m qui transforme s en q. Si \varphi existe, nous devons donc avoir

\varphi(q)=\varphi(s\cdot m)=s_L\cdot m=m^{-1}\cdot L=q^{-1}\cdot F

Ainsi, comme annoncé, il y n’y a qu’un seul \varphi possible et nous devons vérifier que, \varphi étant défini par la dernière relation, il répond aux conditions de l’énoncé.

Les états de \mathcal A(L) étant les langages m^{-1}\cdot L,\ m\in A^*, \varphi est évidemment surjectif. De plus,

\varphi(s)=s^{-1}\cdot F=L=s_L

et, pour tout n\in A^*,

\varphi(q\cdot n)=(q\cdot n)^{-1}\cdot F=n^{-1}\cdot (q^{-1}\cdot F)=\varphi(q)\cdot n

Pour conclure la démonstration, occupons nous des états finals. Compte tenu de l’accessibilité de \mathcal A, un état q\in Q  est final si, et seulement si, on peut transformer s en q par un élément de L. Cela revient au même de dire qu’il existe m\in L tel que \varphi(q)=m^{-1}\cdot L ce qui, à son tour, équivaut au fait que \varphi(q) est un état final dans \mathcal A(L).

La cause est donc entendue.

Un premier pas vers le théorème de Kleene

Le théorème de Kleene identifie les langages qui sont acceptés par des automates finis déterministes. Il sera énoncé et prouvé ailleurs mais ce qui précède nous donne l’occasion de déjà faire une remarque significative concernant ces langages.

La famille des langages sur un alphabet qui sont acceptés par un automate fini déterministe est stable par union finie, concaténation et étoile de Kleene.

Vu (1), un langage est accepté par un automate fini déterministe si, et seulement si, son automate minimal est fini. Nous devons donc vérifier que si les automates minimaux de langages L_1,L_2,L sur un alphabet A sont finis, il en va de même de ceux de L_1\cup L_2, L_1L_2 et de L^* .

Pour l’union , c’est immédiat car il est évident que

Q(L_1\cup L_2)\subset \left\{q\cup q'| q\in Q(L_1), q'\in Q(L_2)\right\}

Pour la concaténation, on établit d’abord l’égalité suivante, où m\in A^* :

m^{-1}\cdot (L_1L_2)=(m^{-1}\cdot L_1)L_2\cup \bigcup_{uv=m,u\in L_1}v^{-1}\cdot L_2

Elle montre que Q(L_1L_2) est constitué d’union d’éléments de Q(L_2) et d’ensembles de la forme qL_2, où q\in Q(L_1). Il est donc fini si Q(L_1) et Q(L_2) sont finis.

Pour l’étoile de Kleene une formule similaire permet de conclure de façon semblable, à savoir

m^{-1}\cdot L^*=\bigcup_{uv=m,u\in L^*}(v^{-1}\cdot L)L^*

si m\notin L^* et, sinon,

m^{-1}\cdot L^*=\{\varepsilon\}\cup\bigcup_{uv=m,u\in L^*}(v^{-1}\cdot L)L^*

Les preuves de ces formules sont aisées. Elles sont omises.

Réduction

Soit un état q d’un automate. Le langage q^{-1}\cdot F est celui qu’accepterait l’automate si on prenait q pour état initial. On dit pour cela que c’est le langage accepté depuis q. L’automate définit ainsi une famille de langages et le langage qu’il accepte se distingue des autres uniquement par le choix de l’état initial. Lorsque tous ces langages sont différents, ils permettent de discerner les états de l’automate. On dit alors que celui-ci est réduit.

L’automate minimal d’un langage L est réduit. En effet, si q=m^{-1}\cdot L, alors u appartient à q^{-1}\cdot F(L) si, et seulement si, mu\in L. Par suite q^{-1}\cdot F(L)=q.

Un automate est minimal si, et seulement si, il est accessible et réduit.

Je ne l’ai pas encore précisé mais on convient de ne pas distinguer deux automates qui ne diffèrent que par les noms de leurs états. De façon plus rigoureuse, deux automates sont considérés comme étant les mêmes s’ils sont isomorphes, c’est-à-dire s’il existe une bijection entre leurs ensembles d’états qui échangent les actions, les états initiaux et les états finals.
C’est avec cette notion qu’il faut comprendre l’énoncé ci-dessus : un automate « est minimal » s’il est isomorphe à l’automate minimal du langage qu’il accepte.

Nous avons déjà observé que l’automate minimal d’un langage est accessible et réduit. Comme ces caractéristiques sont conservées par isomorphisme, il reste, pour démontrer la propriété, à s’assurer qu’un automate \mathcal A accessible et réduit est minimal. D’après la propriété (1) et sa démonstration, q\mapsto q^{-1}\cdot F est une application surjective de l’ensemble des états de \mathcal A sur celui de l’automate minimal du langage qu’il accepte. Elle échange les actions, les états initiaux et les états finals des deux automates. Comme \mathcal A est réduit, elle est injective. C’est donc un isomorphisme : \mathcal A est minimal.

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