Intro

Théorème :

Pour toute automate finie non détérministe on peut construire un AFD equivalent

1) Elimination des transitions sur des mots de longueurs <1

2) photo

Algorithme D’élimination des transition de longueur >1

Donnée A = (Q, Σ,^, S,F)

A’ = (Q’, Σ, ^’, S,F) tq pour tout ( q,u,q’) in ^’

1. Initilisation : Q’ = Q , ^’=^
2. Pour tout (q,u,q’) in ^’ ta |u| > 1 avec u = u1…uk
3. Eliminer les (q,u,u’) de ^’
4. ajouter les états intermédiaires p1,….,^pk
5. Ajouter les transitions (q,u1,p1), (pk-1, uk, q’) et (pc,ui+1,pi+1) pour i =1…..k-2

Algorithme d’élimination des transitions compatibles

Donnée un AFND A = ( Q,Σ, ^ ,S ,F ) ou pour tout (q,u,q’)

un AFD A’ = (Q’,Σ,δ’, s’,f’) équivalent à A avec |u| ≤ 1

1. Q’ = $2^Q$
2. S’ = E(S)
3. δ’(q, 6) = U { E(p) | il existe q in q’ , (q,6,q) in ^ }