Théorème de Kleene

De
Publié par

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


Publié le : mardi 19 juin 2012
Lecture(s) : 78
Source : deptinfo.unice.fr
Nombre de pages : 4
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(%+&)
* Suite preuve(opération )
! ' Areconnaît le langage décrit par%
Expressions régulières
Définition inductive(B)... (I)si%,&#ERalors  ...  ... ' %#ER
Exemple
Y =bY +aY 2 14
$
A % $ $
2 bY =$+ aY +bY 4 44 Y =bY +aY 1 23a b 4 1b a,b a a
Y =$+aY +bY 3 42
$ A
Y décritle langage des mots w q * tels que((q,w)#F * (: prolongement de(aux mots
Passage dun A.F.D. à une E.R.
Réciproquement, à partir dun A.F.D, peut-on construire une expression régulière qui décrit le langage reconnu parA?
Lessystèmes déquations linéaire à droitepermettent de ramener le calcul dune exp.rég. à la résolution dun système déquations.
A chaque étatqon associe une expression régulièreY q dénotant le langageL (A)associé à cet état. q On obtient un système déquations dont lesinconnuessont des exp.rég. dénotant deslangages.
Siqest létat initial,Ydécrit le langage reconnu parA. q
Attention !!!
Ne pas oublier les$...
Exemple
Y =bY +aY 1 2 3
Y =bY +aY 2 1 4 Y =$+ aY+ bY 3 42 Y =$+(a+b)Y 4 4
Résoudre un tel système revient à calculerY, car il est associé 1 à létat initial1. On procède par substitutions et on va avoir besoin de résoudre léquation : Y = A Y + B
Equation Y= A Y + B
' A Best bien solution : ''+' BA B = A AB + B = AB + B = A
' A Best une solutionminimale:
' si Y est une solution, alors AB)Y
Récurrence sur la hauteur détoile : 0 - si i=0, A B = B)Y car Y = AY + B n- hyp. réc. pour i=n : A B)Y n+1 nB = A A B- pour n+1 : A)A Y)A Y + B = Y, cqfd.
Exemple * On garde toujours à lesprit que si$*A alorsABest lunique solution de Y=AY+B.
Y =bY +aY 1 2 3 2 Y =bY +aY b2 1 4 a Y =$+bYaY + 3 42 b Y =$+(a+b)Y 4 4 a,b 4 1 b
a
3
a
+
Y =(a+b)* 4
(Y estalors éliminé) 4
Equation Y= A Y + B(suite)
' si$*AB est lalors Aunique solution.
' On suppose la non-unicité de la solution AB. Soit X une autre solution '  \A et soit un mot w de longueur minimale tel que w#XB.
w#X=AX+B et w*B donc w=uv avec u#A et v#X. ' ' Or v*A B(sinon w aussi) donc v#X\A B. Contradiction : la longueur de w nétait donc pas minimale !
si$#Aalors pour tout C)!,Y =+ ACA Best aussi solution : *' ' B + AC = A (A+ AA BB + AC + B = AB + AC) + B = AB + AC = AC' '' '+ +'+' '
si lautomate de départ estdéterministe, on a toujours :$*A
Exemple
a(a+b)* 2 b b 1 b
a
3 a(a+b)*
Y =bY +aY 1 2 3 Y =bY +a(a+b)* 2 1 * Y =$+bYa(a+b) + 3 2
+
* Y =bbY+ ba(a+b)+ aY 113 * Y =$+a(a+b) +bbY+ba(a+b)* 31
(Y estalors éliminé) 2
Exemple * On garde toujours à lesprit que si$*A alorsABest lunique solution de Y=AY+B.
ba(a+b)*
bb 1
a
bb
3 (b+$)a(a+b)*
* Y =bbY +ba(a+b) +aY 1 13 * Y =$+(b+bbY +$)a(a+b) 3 1
+
* Y =bbY +ba(a+b) + 1 1 *  a$+abbY+a(b+$)a(a+b) 1
(Y estalors éliminé) 3
Exemple On garde toujours à lesprit que si$*A alorsABest lunique solution de Y=AY+B. *
s abb bb 1
Y =(abb+bb)Y + 1 1 * * a(ba(a+b) +$+(b+$)a(a+b) ) +
** * Y =(abb+bb)(ba(a+b) +a($+(b+$)a(a+b) )) 1
a($+(b+$)a(a+b)*)
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.