Automates et langages formels V – Langages réguliers et le théorème de Kleene (b)

Le théorème de Kleene identifie les langages qui sont acceptés par les automates finis.

Compte tenu de ce que nous savons déjà, nous allons pouvoir rapidement prouver que les langages réguliers, encore appelés langages rationnels — j’espère ne pas oublier d’expliquer l’origine de cette dénomination, sont acceptés par des automates finis. C’est à ces langages qu’est consacré le présent billet. Dans un autre, nous établirons la réciproque, achevant ainsi la preuve du théorème de Kleene.

Les langages réguliers

Etant donné un alphabet A, notons \mathcal R(A) le plus petit ensemble de parties de A^* qui soit stable par union, concaténation et étoile de Kleene et qui contienne les langages

\varnothing \quad \& \quad \{a\}, a\in A

Par définition, les éléments de \mathcal R(A) sont les langages réguliers sur A.

Théorème de Kleene. Un langage sur un alphabet est accepté par un automate fini déterministe si, et seulement si, il est régulier sur cet alphabet.

Dans ce billet, nous avons montré à l’aide de la notion d’automate minimal que l’ensemble des langages acceptés par les automates finis déterministes d’alphabet A est stable par union, concaténation et étoile de Kleene. Le langage accepté par l’automate suivant

regulier_1

est le langage vide(*). Pour chaque lettre a\in A, l’automate

accepte quant à lui le langage \{a\}. Il est donc clair que chaque langage régulier sur A est accepté par un automate fini déterministe d’alphabet A.

Comme annoncé, je donnerai la réciproque plus tard. Il y a plusieurs façon de l’établir. Celle que j’ai en vue est liée à certains aspects de la notion de structure de données. C’est pourquoi je préfère lui consacrer un autre billet. Dans l’immédiat, nous allons voir que les langages réguliers sont caractérisés par des syntaxes bien spécifiques, ce qui nous sera d’ailleurs utile pour établir la réciproque en question.

Expressions régulières

Dans ce qui suit, le signe « + », la concaténation et l’étoile « * » placée en exposant jouent le même rôle que l’addition, la multiplication et l’exponentiation dans les formules de l’arithmétique de \mathbb R.

J’entends par là qu’on va considérer les expressions construites avec ces « opérations », avec les parenthèses, deux nouveaux symboles et les mots sur un alphabet A, en respectant les mêmes règles de formation que celles qui régissent les expressions algébriques usuelles fabriquées avec l’addition, la multiplication, l’exponentiation et des lettres sensées représenter des nombres.

Les symboles ajoutés — ils joueront des rôles similaires à ceux tenus par les neutres de l’addition et de la multiplication — sont notés 0, e(**).

Ces expressions, des mots particuliers sur l’alphabet A\cup\{(,),+,0,e\}, sont les expressions régulières sur l’alphabet A. En voici quelques exemples lorsque A=\{a,b\} :

a^*b^*, (a+bab)b^*, (a+b)^*, (ab^*)^*,e+(b(aa)^*b)^*,...

Ces expressions sont interprétées en attribuant les mêmes priorités que celles que possèdent l’addition, la multiplication et l’exponentiation dans les expressions arithmétiques familières. Mais, à la différence de celles-ci, dont l’évaluation sur des valeurs spécifiques des variables sont des nombres, les expressions régulières représentent des langages sur A : à chaque expressions régulière \alpha sur A est associé un langage L(\alpha)\subset A^*. Il est défini récursivement comme suit.

On pose tout d’abord

L(0)=\varnothing \quad \& \quad L(e)=\{\varepsilon\}

et, pour tout mot m\in A^*, L(m)=\{m\}. Ensuite, si \alpha, \beta, \alpha+\beta, \alpha\beta ou \alpha^* sont des expressions régulières,

L(\alpha+\beta)=L(\alpha)\cup L(\beta), \quad  L(\alpha\beta)=L(\alpha)L(\beta)) \quad \& \quad L(\alpha^*)=L(\alpha)^*

Par exemple,

L((a+b)^*)=L(a+b)^*=(L(a)\cup L(b))^*=\{a,b\}^*

ou encore, L(a^*b^*)=\{a^pb^q|p,q\in \mathbb N\}. Cela étant,

Les langages réguliers sur un alphabet sont exactement les langages associés aux expressions régulières sur celui-ci.

Ceci est facile à voir.

Tout d’abord, il découle aisément de la définition du langage L(\alpha) associé à une expression régulière \alpha que l’ensemble \mathcal L des langages associés aux expressions régulières sur un alphabet A est stable par union, concaténation et étoile de Kleene et qu’il contient les langages \varnothing et \{a\}, a\in A. En conséquence : \mathcal R(A)\subset \mathcal L.

Pour établir l’inclusion réciproque, il suffit de vérifier que si \mathcal M est un ensemble de langages sur l’alphabet A qui est stable par union, concaténation et étoile de Kleene et qui contient \varnothing et les langages \{a\}, a\in A, alors \mathcal L\subset \mathcal M.

On procède par récurrence sur la longueur de \alpha pour vérifier que L(\alpha)\in\mathcal M. Pour les expressions régulières de longueur un (il n’y en a pas de plus courtes), c’est clair car \{a\}=L(a) pour toute lettre a et

L(0)=\varnothing \quad \& \quad L(e)=\{\varepsilon\}={\varnothing}^*

Pour des expressions \alpha plus longues, L(\alpha) est union, concaténation ou étoile de Kleene de langages associés à des expressions plus courtes et on utilise la stabilité de \mathcal M sous ces opérations pour conclure.

Avec le théorème de Kleene, ce résultat permet de vérifier ce que j’avais annoncé ici des caractères de divisibilité : ils sont de nature purement syntaxique. En effet, les expressions en base b des nombres divisibles par d sont acceptées par un automate fini déterministe que nous avons noté \mathcal A(b,d). Le langage accepté par cet automate est régulier. Il est donc associé à une expression régulière. Celle-ci décrit la syntaxe caractéristique à laquelle obéissent les expressions en base b des multiples de d.

On confond souvent le langage L(\alpha) et l’expression régulière \alpha à laquelle il est associé. C’est commode et, sauf rares exceptions, cela ne prête guère à confusion.

Les langages réguliers sur un alphabet à une lettre

Ces langages ont une forme très simple que nous sommes en mesure de trouver aisément.

Voici un automate dont l’alphabet est réduit à une lettre, a.

regulier_3

Il accepte le langage(***)

a+(a^6+a^8)(a^9)^*=\{a\}\cup\{a^{6+9n}|n\in\mathbb N\}\cup\{a^{8+9n}|n\in\mathbb N\}

Sa forme particulière, familièrement appelée poêle à frire, est caractéristique des automates finis accessibles sur l’alphabet \{a\}.

En effet, les états d’un tel automate \mathcal A sont

s,s\cdot a,s\cdot a^2,s\cdot a^3,...

où, comme d’habitude, s désigne l’état initial.

Comme ils sont en nombre fini, il existe n<m tels que s\cdot a^n=s\cdot a^m. On prend n, m aussi petits que possible. Le « manche » de la poêle à frire représentant \mathcal A est alors constitué des états s,...,s\cdot a^{n-1} tandis que le cycle est formé par les états s\cdot a^n,...,s\cdot a^{m-1}.

Un état final s\cdot a^p permet d’accepter le seul mot a^p s’il est dans le manche et les mots a^{p+nq}, n\in \mathbb N, s’il est dans le cylce, q étant le nombre d’arcs de ce dernier.

Un langage sur l’alphabet \{a\} est régulier si, et seulement si, c’est une union finie d’ensembles de la forme

a^p(a^q)^*=\{a^{p+nq}|n\in\mathbb N\}

p et q sont des entiers positifs ou nuls.

En effet, ces ensembles sont réguliers, puisqu’ils sont décrits par des expressions régulières, et nous venons de voir que les langages acceptés par automates finis sur \{a\} sont de cette forme(****).

__________
(*) Lorsque l'étiquette d'un arc est une propriété, il symbolise un ensemble d'arcs de mêmes début et fin et dont les étiquettes sont les lettres vérifiant la propriété.
(**) On suppose implicitement que ces lettres, de même que les parenthèses et +, ne figurent pas déjà dans A. Si c'était le cas — dans les systèmes de numération, 0 est souvent dans l'alphabet, on conviendrait d'utiliser d'autres symboles à leur place.
(***) La notation u^p est un raccourci commode pour désigner la concaténation de p copies du mot u.
(****) L’ensemble \varnothing est l’union de la famille vide d’ensembles de la forme indiquée.

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