[THL] Theorie des langages (3)

// notes de cours

Automate a etats finis : Possede un nombre fini d’etats







hierarchy



qi




0

0



qi->0





qj




0->0


a,b



1

1



0->1


a



2

2



1->2


a,b



2->qj





Peut se transcrire en l’automate infini suivant







hierarchy



qi




0

0



qi->0





0 

0 



0->0 


b



01

01



0->01


a



0  

0  



0 ->0  


b



01 

01 



0 ->01 


a



0   

0   



0  ->0   


b



 01 

 01 



0  -> 01 


a



012

012



01->012


a



02

02



01->02


b



 01

 01



02-> 01


a



 0

 0



02-> 0


b



Automate deterministe a etats finis (DFA) :







hierarchy



qi




0

0



qi->0





qj




qk




0->0


b



01

01



0->01


a



012

012



01->012


a



02

02



01->02


b



012->qj





012->012


a



012->02


b



02->qk





02->0


b



02->01


a



On a plus qu’une seule entree Plus qu’un seul choix possible par etat

-> Programme de complexite lineaire

Table de transition DFA :

T a b
0 1 0
1 2 3
2 2 3
3 1 0

Ou 0:0 01:1 012:2 12:3







hierarchy



qi




0

0



qi->0





qj




0->0


a,b



1

1



0->1


a



2

2



1->2


a,b



2->qj





Table de transition depuis NFA:

T a b
0 01 0
01 012 02
012 012 02
02 01 0

L.Rat -> Expr Rat -> NFA -> NFA -> DFA

Algorithme de Boyer-Moore


2 derniers symboles vus par noeud

T a
0 bb
01 ba
012 aa
02 ab

Memoire de l’automate



Les automates (Expr Rat -> NFA -> NFA -> DFA) ne marchent que sur des langages rationnels.

Lemme de pompage
Condition necessaire de rationalite

Le complementaire preserve la rationnalite