Théorème de Kleene

pefav - Sandrine Julia

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

4 pages

Français

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

A propos
Informations
Extrait

Description

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

Sujets

Expression rationnelle

Informations

Publié par	pefav
Nombre de lectures	88
Langue	Français

Extrait

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)...

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 inductiveA Expressions régulièresA % A & %(B)... Définition inductive$ (I)si%,&#ERalors (B)... ... A (I)si%,&#ERalors$ &(%.&)#ER $ $ $ (%+&)#ER ... A A ...

! Areconnaît le langage décrit par(%+&)