Théorème de KLEENE
Les événements, que l'on peut décrire à partir d'événements de base en utilisant les trois opérateurs d'union, de concaténation et d'itération, sont exactement ceux que l'on peut spécifier à l'aide d'un automate fini.
Dans [Kleene56], Stephen Cole Kleene (1909-1994) démontre une sorte de théorème de représentation qui établit l'équivalence entre deux modes de définition du même objet. Ces objets sont ce que Kleene appelle les événements réguliers, aujourd'hui souvent appelés langages plutôt qu'événements et qualifiés de rationnels plutôt que de réguliers. Le terme d'événement renvoie bien sûr à la terminologie du calcul des probabilités mais aussi au point de vue de départ de cette théorie qui s'adresse à la description de phénomènes plutôt qu'à la spécification de propriétés formelles, comme de nos jours.
Les événements réguliers sont ceux que l'on peut décrire à partir d'événements de base en utilisant les opérateurs de :
Il est possible de construire un AFN reconnaissant un langage rationnel par induction à partir des symboles et des trois opérateurs de base. En effet, si l'on reprend d'une part le lemme du langage réduit à un mot et d'autre part les théorèmes du produit cartésien (×), de la mise à l'étoile (*) et de l'union (∪), à toute étape de la construction d'un langage rationnel correspond la construction d'un automate fini reconnaissant le même langage. Plus formellement, cela donne :
Pour effectuer le passage d'une expression régulière à un automate fini déterministe minimal, une méthode possible consiste à construire d'abord un AFN reconnaissant le même langage, de le transformer en un AFD équivalent puis, finalement, de le réduire. Pour les deux dernières phases, nous avons déjà présenté une méthode adaptée. Intéressons-nous désormais à la phase de construction de l'AFN à partir d'une expression régulière. Le processus inverse est aussi possible. Nous verrons cela plus loin.
Il n'est pas toujours aisé de prouver qu'un langage (souvent décrit pas une expression) est rationnel. Nous avons déjà présenté quelques idées. Le théorème de Kleene nous permet de proposer une autre stratégie.
Pour montrer qu'un langage est rationnel, il suffit de construire un automate fini reconnaissant ce langage. Parfois, la construction de cet automate est plus aisée que la construction d'une expression rationnelle standard.
|
|
Le complémentaire d'un langage rationnel est un langage rationnel L'intersection de deux langages rationnels est un langage rationnel |
Démonstrations
Pour la première partie, il suffit de se rappeler que le complémentaire d'un langage reconnaissable est un langage reconnaissable. Si on ajoute à cela le théorème de Kleene CQFD
Pour la second partie, il suffit de se rappeler que l'intersection de deux langages reconnaissables est un langage reconnaissable. Si on ajoute à cela le théorème de Kleene CQFD
Grâce au théorème de Kleene, il est possible de déduire qu'à tout automate fini il est possible d'associer une grammaire linéaire droite.
|
|
Soit T un AFN tel que $L(T)=L$ alors il existe une grammaire linéaire droite $LD$ telle que $L=L(LD)$. |
Dém. (par construction)
Une dérivation de la grammaire correspond à un mouvement de l'automate. Soit T=(A, Q, I, F, μ), on pose G=(A, Q, I, S) où S est défini par :
vendredi, 19/09/03 15:26