LA COMPILATION
Section : SMI - Semestre 5
A.U: 2020-2021
[Link]@[Link]
1
RÉCAPITULATIF
langage explicite <-—>expression régulière ———> NFA-ℇ
Théorème 4
➤
Théorème 3
4
é o rème
T h
Théorème 1 Théorème 2
DFA avec nombre minimal d’état <——— DFA <———NFA
Théorème 4: Un langage est régulier si et seulement s’il est accepté
par un DFA.
➤ démonstration du théorème 4 dans l’autre sens :
73
DES AUTOMATES AUX EXPRESSIONS RÉGULIÈRES
➤ Soit M= (Q , ∑ , 𝛿 , q1, F) un DFA et Q={q1 , q2 … , qn } avec n : le nombre des états.
On désigne par R(i,j,k) l’ensemble des mots permettant de passer de l’état qi à qj en
passant uniquement par des états { q1 , q2 … , qk-1} (d’indice < k).
R(i , j ,1)={ s de ∑ / 𝛿(qi , s)=qj } si i ≠j }
R(i , i ,1)={ℇ} ∪ { s de ∑ / 𝛿(qi , s)=qi }
Pour K >1,
R(i , j , k+1)= R(i,j,k)∪ R(i,k,k).R(k,k,k)*.R(k,j,k)
l’r.e qui dénote R(i , j , k+1) sera: r(i,j,k+1) = r(i,j,k) | r(i,k,k).r(k,k,k)*.r(k,j,k)
Noter bien :
L(M)= est un langage régulier (stabilité par ∪ . et *))
Donc pour déterminer l’exp. rég. qui décrit L(M) il sufXit de déterminer celles de
R(1,j,n+1) pour tout qj état Xinal que nous notons r(1,j,n+1) 74
EXEMPLE:
➤ Soit le DFA représenté par le graphe:
Pour K=1 ; r(i,j,1) sont donné par le tableau:
Pour k=2 ; r(i,j,2)= r(i,j,1) | r(i,1,1).r(1,1,1)*.r((1,j,1)
Remplir le tableau des r(i,j,2) suivants:
r(2,2,2)=r(2,2,1) | r(2,1,1).r(1,1,1)*.r(1,2,1)
= ℇ |0| 1.1*.0 = ℇ |1*.0
75
➤ les r(i,j,2) sont :
➤ Pour l’r.e équivalente à notre DFA: r(1,2,3) qui dénote L(R(1,2,3)
(car 1 est l’état initial, 2 est l’état final et le nombre des états +1 = 3)
r(1,2,3) = r(1,2,2)| r(1,2,2).r(2,2,2)*.r((2,2,2)
= 1*0 | 1*0.(ℇ |1*0)*.(ℇ |1*0)
= 1*0 | 1*0.(1*0)*.(ℇ |1*0)
= 1*0 |(1*0)+.(ℇ |1*0)
= 1*0 |((1*0)+|(1*0)+.(1*0))
=1*0|(1*0)+ = (1*0)+
r+ ou r+.r {r, rr, rrr, rrrr …} ou {rr, rrr, rrrr, ….}
76
LES GRAMMAIRES HORS
CONTEXTE
77
