Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

 2- Théorème de Kleene
Stephen C. Kleene Mathématicien et logicien américain 1909-1994
Suite preuve(opération +)
Théorème de Kleene
Théorème :Un langage sur un alphabet!est rationnel si et seulement si il est reconnu par un automate fini.
Premier sens : preuve par induction
! On cherche des A.F.N pour chaque langage régulier dénoté par les expressions régulières de base
Expressions régulières Définition inductive(B) "#ER $#ER a#ER, pour tout a# ! (I)...
a
Suite preuve(opération .)
! !Areconnaît le langage décrit par(%.&)par hypothèse dinduction, on suppose quil existe deux A.F.N. AetAtels que L(A) est le langage décrit par lexp.rég.%% &% et L(A) celui décrit par lexp.rég.&. & Expressions régulières$ Définition inductiveA Expressions régulièresA % A & %(B)... Définition inductive$ (I)si%,&#ERalors (B)...  ... A (I)si%,&#ERalors$ &(%.&)#ER $ $ $ (%+&)#ER ... A A  ...
! Areconnaît le langage décrit par(%+&)