Automates et langages formels VI – Inéquations

Dans les « épisodes » précédents, nous avons fait connaissance avec les automates déterministes — et en particulier, la notion d’automate minimal, les langages formels — et en particulier, les langages réguliers, puis avec les expressions régulières.

Nous avons appris que les langages réguliers sont les langages acceptés par les automates finis déterministes (mais nous ne l’avons pas encore complètement prouvé) et qu’ils sont décrits par les expressions régulières.

Nous avons illustré certains de ces concepts avec l’automate \mathcal A(b,d) acceptant les expressions en base b des multiples de d . Nous avons par exemple établi qu’il est minimal si, et seulement si, b et d sont premiers entre eux. Nous savons également que ces expressions obéissent à une syntaxe spécifique mais il nous faut encore expliquer comment obtenir effectivement une expression régulière la décrivant.

Dans ce billet, nous allons établir quelques propriétés des systèmes d’inéquations à coefficients réguliers avec lesquelles nous pourrons achever la preuve du théorème de Kleene et construire des expressions régulières décrivant le langage accepté par un automate fini déterministe.

L’algèbre des expressions régulières

Pour nous simplifier la vie, nous avons convenu de parfois désigner de la même façon une expression régulière et le langage qu’elle décrit. Cela nous incite à considérer comme équivalentes deux expressions régulières décrivant le même langage, relation que nous désignerons par le signe d’égalité.

Avec cette convention, en transposant les propriétés des opérations sur les langages, on obtient une sorte d’algèbre sur les expressions régulières. Elle est assez difficile à étudier(*), et je me contenterai de signaler les formules suivantes. Elles nous permettront à l’occasion de simplifier certaines expressions régulières et de poser et résoudre des équations ou des inéquations sur l’ensemble des langages réguliers.

La vérification de ces formules est intéressante à faire pour se familiariser avec les expressions régulières. Je vais donc laisser à chacun la possibilité de s’exercer en les prouvant lui-même.

Dans ces formules, \alpha,\beta,\gamma représentent des expressions régulières sur un alphabet donné. Les voici :

(i) \alpha(\beta\gamma)=(\alpha\beta)\gamma, \alpha(\beta+\gamma)=\alpha\beta+\alpha\gamma, (\beta+\gamma)\alpha=\beta\alpha+\gamma\alpha, \alpha+\alpha=\alpha

(ii) 0\alpha=\alpha 0=0,0+\alpha=\alpha+0=\alpha,e\alpha=\alpha e=\alpha

(iii) \forall k\in \mathbb N,\quad \alpha^*=\alpha^0+\alpha^1+\cdots+\alpha^k+\alpha^{k+1}\alpha^*

(iv) 0^*=e,\quad \alpha^{**}=\alpha^*

(v) (\alpha+\beta)^*=(\alpha^*\beta)^*\alpha^*

Une inéquation à une inconnue

Une inéquation (régulière) à une inconnue est une expression de la forme

x\geqslant \alpha x+\beta

dans laquelle \alpha et \beta sont des expressions régulières sur un alphabet A .

Une solution de cette inéquation est un langage X\subset A^* vérifiant l’inclusion X\supset \alpha X\cup\beta. Elle est exacte si cette inclusion est une égalité et elle est minimale si elle incluse à toute autre solution.

Par définition, l’inéquation admet au plus une solution minimale. Nous allons voir qu’en fait, elle en admet une, et que celle-ci est exacte et régulière.

Pour commencer, en appliquant les propriétés ci-dessus, on observe que \alpha^*\beta est une solution exacte car

\alpha(\alpha^*\beta)+\beta=(\alpha\alpha^*)\beta+\beta=(\alpha\alpha^*+e)\beta=\alpha^*\beta

Ensuite, toute solution inclut \beta et dès lors \alpha^k\beta pour tout k\in\mathbb N. Ainsi \alpha^*\beta est inclus à toute solution de l’inéquation et en est donc bien une solution minimale.

Ce que nous venons de prouver appelle quelques commentaires.

— D’une certaine façon, l’étoile de Kleene se substitue à l’inverse de e-\alpha. Tout se passe en effet comme si on pouvait résoudre heuristiquement l’équation x=\alpha x+\beta en s’inspirant de la manière dont on résout une équation numérique : on isole l’inconnue dans un membre

(e-\alpha)x=\beta

puis on divise les deux membres par e-\alpha, en calculant son inverse en utilisant la série géométrique de raison \alpha :

x=(e-\alpha)^{-1}\beta=(\sum_{k\in\mathbb N}\alpha^k)\beta=\alpha^*\beta

Il existe un cadre théorique dans lequel ce procédé est tout à fait légitime, théorie remarquablement exposée dans le livre de Christophe Reutenauer : Sur les séries rationnelles en variables non commutatives, Springer Lecture Notes in Computer Sciences, 1978.

Dans ce cadre, l’union, la concaténation et l’étoile de Kleene sont vus comme des instances particulières de ce qu’on appelle les opérations rationnelles, opérations avec lesquelles on définit une notion très abstraite de série rationnelle en variables non commutatives qui généralise la notion habituelle de fraction rationnelle sur \mathbb C et dont les langages réguliers constituent un autre cas particulier(**).

— En informatique, les structures linéaires constituent une classe importante de structures de données : pile, queue, etc. Elles sont définies en spécifiant les opérations autorisées sur les suites finies d’objets d’un certain type, lesquelles sont définies récursivement, par des prescriptions du genre

Un élément de type E est soit un élément de type A suivi d’un élément de type E soit un élément de type B.

Cette définition autorise à trouver dans E des suites infinies d’éléments de type A mais le caractère effectif de l’informatique les élimine. Il ne reste alors dans E que les éléments de la forme a_1\cdots a_nb où les a_i appartiennent à A et b est un élément de B.

Ainsi, l’équation x=\alpha x+\beta symbolise la définition récursive des structures de données linéaires tandis que sa solution minimale représente la structure de donnée effectivement décrite par une telle définition(***).

Systèmes d’inéquations

Ce qui précède s’étend aux systèmes de p inéquations à p inconnues

(1) x_i\geqslant \sum_{1\leqslant j\leqslant p}\alpha_{ij}x_j+\beta_i,\quad 1\leqslant i\leqslant p

dont les coefficients sont des expressions régulières sur A .

Une solution est cette fois une suite X=(X_1,...,X_p) de p langages sur A vérifiant

X_i\supset \left(\bigcup_{1\leqslant j\leqslant p}\alpha_{ij}X_j\right)\cup\beta_i,\quad 1\leqslant i\leqslant p

Elle est exacte si ces inclusions sont des égalités et minimale si, pour toute solution Y, on a X_i\subset Y_i pour tout i\in\{1,...,p\} .

Le système (1) admet une seule solution minimale. Elle est exacte et ses composantes sont des langages réguliers sur A .

Ceci est facile à vérifier par récurrence sur le nombre d’inconnues. Le cas d’une inconnue a été traité plus haut et, pour l’induction, on procède par élimination successives des inconnues, ce qui donne en prime des expressions régulières décrivant les langages composant la solution minimale.

Pour éliminer x apparaissant dans une inéquation de la forme x\geqslant ux+v, on le remplace par u^*v dans les autres.

Je ne ferai pas la preuve en détails. Je vais plutôt montrer sur l’exemple

\left\{\begin{array}{lcl}x_1&\geqslant&ax_1+bx_2+e\\x_2&\geqslant&ax_1+bx_3+e\\x_3&\geqslant&(a+b)x_3\end{array}\right .

comment obtenir la solution minimale par éliminations successives.

Dans la dernière inéquation, le terme indépendant est nul. On remplace donc partout x_3 par (a+b)^*0=0. La deuxième inéquation devient alors

x_2\geqslant ax_1+e

Dans le membre de gauche de cette inéquation, le coefficient de x_2 est nul, ce qui conduit à poser

x_2=0^*(ax_1+e)=ax_1+e

Reporté dans la première inéquation, celle-ci devient

x_1\geqslant ax_1+bax_1+b+e=(a+ba)x_1+b+e

et donne ainsi x_1=(a+ba)^*(b+e), une expression régulière représentant l’ensemble des mots sur \{a,b\} ne comportant pas deux b consécutifs.

Finalement, la solution minimale cherchée s’écrit, en termes d’expressions régulières,

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

__________
(*) Il me semble avoir lu qu’elle ne peut être définie par une axiomatique finie. Malheureusement, je ne sais dans quel livre! Désolé!
(**) C’est pourquoi expressions régulières et langages réguliers sont aussi appelés expressions et langages rationnels.
(***) Des structures de données plus complexes, les arbres par exemple, ont également des interprétations symboliques dans le cadre de la théorie des langages formels. Elles mettent en jeu des syntaxes plus élaborées que celle des expressions régulières, correspondant à des niveaux plus élevés de la hiérarchie de Chomsky.

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