[THL] Theorie des langages (2)

Automates









hierarchy







:)

:)



->:)


a



:(

:(



->:(


!a




Concatenation . :







hierarchy



L1

L1



L2

L2



L1->L2


:)







L1->


:(



:(

:(



L2->:(





:)

:)



L2->:)





Machine a etats :

Σ : Langage
Q : Etats
ICQ : Etats d’entree
FCQ : Etats finaux
S : Transitions

Automate de







hierarchy



qi








qi->





L1

L1



->L1


ε



L2

L2



->L2


ε



 

 



L1-> 


ε



L2-> 


ε




Automate deterministe

Objectif : rendre cet automate deterministe







hierarchy



qi




0

0



qi->0





qj




1

1



0->1


ε



7

7



0->7


ε



6

6



0->6


n



8

8



0->8


n



3

3



0->3


a



2

2



1->2


ε



4

4



1->4


ε



7->8


n



13

13



6->13


ε



9

9



8->9


ε



3->2


ε



3->4


ε



10

10



9->10


ε



12

12



9->12


ε



11

11



10->11


a



11->10


ε



11->12


ε



12->13


ε



13->qj





2->3


a



5

5



4->5


ε



5->6


n



Epsilon fermeture : tous les etats auquels om peut acceder sans consommer de charactere

On liste les etats et leurs transitions epsilon

εf() 1 2 3
0 0, 1, 7 0, 1, 2, 4, 7 0, 1, 2, 4, 7
1 1, 2, 4 1, 2, 4, 5 1, 2, 4, 5
2 2 2 2
3 3, 2, 4 3, 2, 4, 5 3, 2, 4, 5
4 4, 5 4, 5 4, 5
5 5 5 5
6 6, 13 6, 13 6, 13
7 7 7 7
8 8, 9 8, 9, 10, 12 8, 9, 10, 12, 13
9 9, 10, 12 9, 10, 12, 13 9, 10, 12, 13
10 10 10 10
11 11, 10, 12 11, 10, 12, 13 11, 10, 12, 13
12 12, 13 12, 13 12, 13
13 13 13 13

Resultat :







hierarchy



qi




0

0



qi->0





qj




qk




qq




3

3



0->3


a



6

6



0->6


n



8

8



0->8


n



3->3


a



3->6


a



6->qk





8->qj





11

11



8->11


a



11->qq





11->11


a



Un etat est dit utile si il est a la fois accessible et co-accessible
Emonder un automate : Supprimer les etats non-accessibles ou non co-accessibles