Automates et langages formels VII – Le théorème de Kleene (c)

On peut caractériser chaque automate fini déterministe par un système d’inéquations régulières dont la solution minimale est constituée des langages acceptés depuis les états de l’automate. En particulier, ces langages — et parmi eux le langage accepté par l’automate — sont réguliers. C’est ainsi que s’achève la preuve que je souhaitais vous présenter du théorème de Kleene (énoncé dans ce billet voir également ici).

Avant de détailler , voyons un exemple. Il fournira une réponse au petit problème posé à la fin de cet article.

Le langage de la numération de Zeckendorf

Dans un billet récent, je décrivais la numération de Zeckendorf, obtenue à partir de la suite de Fibonacci.

L’ensemble des mots représentant les entiers positifs ou nuls dans ce système, qu’on appelle le langage de la numération, est construit sur l’alphabet \{0,1\} . Il est formé du mot 0 et des mots commençant par 1 et ne comportant pas le segment 11. Nous y remplacerons désormais 0 et 1 par a et b, pour éviter toute confusion avec le 0 des expressions régulières.

L’automate suivant — nous l’appellerons \mathcal Z — accepte le langage ainsi obtenu.

zeckendorf_1

En effet, si on lit un mot débutant par a à partir de l’état initial, on aboutit à l’état final 2 si le mot ne comporte qu’une lettre et à l’état 4, qui est un puits(*), sinon. Le seul mot commençant par a accepté par \mathcal Z est donc a.

De plus, quel que soit l’état dont on parte, si on lit bb , on tombe dans le puits : les mots commençant par b acceptés par l’automate ne comportent pas ce segment.

Réciproquement, on montre facilement par récurrence sur le nombre de b d’un mot commençant par b que s’il ne contient pas le segment bb , il est accepté par \mathcal Z .

Voici le système d’inéquations associé à \mathcal Z :

\left\{\begin{array}{lcl}x_1&\geqslant&ax_2+bx_3\\x_2&\geqslant&(a+b)x_4+e\\x_3&\geqslant&bx_4+ax_5+e\\x_4&\geqslant&(a+b)x_4\\x_5&\geqslant&bx_3+ax_5+e\end{array}\right.

Il y a une inconnue par état et les seconds membres sont construits à partir des arcs du diagramme de l’automate. Les termes indépendants sont nuls (et donc non écrits) pour les états non finals et valent e pour les états finals.

La méthode présentée à la fin du billet précédent donne aisément sa solution minimale. Dans celle-ci, chaque composante décrit le langage accepté depuis l’état de même numéro. En particulier, la première décrit le langage accepté par l’automate. Voici cette solution :

X=\big(b(aa^*b)^*a^*+a,e,(aa^*b)^*a^*,0,a^*+a^*b(aa^*b)^*a^*\big)

Le langage de la numération de Zeckendorf est ainsi, en revenant aux premières notations,

1(00^*1)^*0^*\cup\{0\}

Par ailleurs, les composantes de X sont toutes distinctes : l’automate \mathcal Z est réduit. Comme, manifestement, il est accessible, il est donc minimal, en application du critère vu ici.

Le théorème de Kleene

Compte tenu de ce qui précède, pour établir le théorème de Kleene, il nous reste à montrer que les langages acceptés par les automates finis déterministes sont réguliers. Voici comment nous allons prouver cela.

Soit un automate fini déterministe \mathcal A = (Q,A,s,F,\delta^*). Convenons de numéroter ses états de 1 à p et de représenter chacun par son numéro, 1 représentant par exemple l’état initial s .

Considérons alors le système

x_i\geqslant \sum_j\sigma_{ij}x_j+\chi_F(i),\quad i=1,...,p

dans lequel \chi_F(i) vaut e ou 0 selon que i est final ou ne l’est pas et dans lequel il y a un terme \sigma_{ij}x_j, avec \sigma_{ij}\neq 0, pour chaque arc joignant i à j et de label \sigma_{ij} .

Il est clair que les langages

L_1=s^{-1}\cdot F=L_{\mathcal A}, L_2=2^{-1}\cdot F,\ldots,L_p=p^{-1}\cdot F

acceptés depuis les états de l’automate forment une solution de ce système. Pour conclure, nous allons voir qu’elle est minimale ce qui suffit, d’après le billet précédent.

Etant donné une solution (X_1,...,X_p), on prouve

\forall k\in\{1,...,p\} : \quad m\in L_k \Longrightarrow m \in X_k

en procédant par récurrence sur la longueur |m| .

Si |m|=0 et m\in L_k, alors m=\varepsilon et k est final. En conséquence, \chi_F(k)=e de sorte que m\in X_k .

Admettons ensuite les conclusions établies pour les mots de longueur < r et considérons un mot m \in L_k de longueur r . Décomposons m=an en la concaténation de sa première lettre a et d’un mot n de longueur r-1 .

Puisque m est accepté depuis l’état k, a=\sigma_{kl}, où l=k\cdot a . Par suite, n\in L_l et, puisque |n|<k, n\in X_l .

De là,

m\in\sigma_{kl} X_l\subset X_k

et la preuve est achevée.

__________
(*) Un puits est un état non final et "dont on ne sort jamais" dans la mesure où il est la fin de tous les arcs dont il est le début.

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