Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Théorème de Kleene

De
4 pages
2 - Théorème de Kleene Stephen C. Kleene Mathématicien et logicien américain 1909-1994 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 (B) _ ER $ _ ER a _ ER, pour tout a _ ! Définition inductive a (I) ... Suite preuve (opération +) ! par hypothèse d'induction, on suppose qu'il existe deux A.F.N. A % et A & tels que L(A % ) est le langage décrit par l'exp.rég. % et L(A & ) celui décrit par l'exp.rég. &. ! A reconnaît le langage décrit par ( % + & ) A % A & $ $ A Expressions régulières Définition inductive (B) ... (I) si %, & _ ER alors ! ( % + & ) _ ER ... Suite preuve (opération .) ! A reconnaît le langage décrit par ( %.

  • récurrence sur la hauteur d'étoile

  • système d'équation

  • automate de départ

  • expressions régulières de base

  • solution minimale

  • expressions régulières

  • hypothèse d'induction


Voir plus Voir moins
 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(%+&)
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin