Théorème d'Arden
Afin de trouver une expression régulière d'un automate fini, nous utilisons le théorème d'Arden avec les propriétés des expressions régulières.
Statement -
Laisser P et Q être deux expressions régulières.
Si P ne contient pas de chaîne nulle, alors R = Q + RP a une solution unique qui est R = QP*
Proof -
R = Q + (Q + RP) P [Après avoir mis la valeur R = Q + RP]
= Q + QP + RPP
Quand on met la valeur de R récursivement encore et encore, nous obtenons l'équation suivante -
R = Q + QP + QP 2 + QP 3 … ..
R = Q (ε + P + P 2 + P 3 +….)
R = QP * [Comme P * représente (ε + P + P2 + P3 +….)]
Par conséquent, prouvé.
Hypothèses pour appliquer le théorème d'Arden
- Le diagramme de transition ne doit pas avoir de transitions NULL
- Il ne doit avoir qu'un seul état initial
Méthode
Step 1- Créez des équations sous la forme suivante pour tous les états du DFA ayant n états avec l'état initial q 1 .
q 1 = q 1 R 11 + q 2 R 21 +… + q n R n1 + ε
q 2 = q 1 R 12 + q 2 R 22 +… + q n R n2
…………………………
…………………………
…………………………
…………………………
q n = q 1 R 1n + q 2 R 2n +… + q n R nn
Rij représente l'ensemble des étiquettes des arêtes de qi à qj, si un tel bord n'existe pas, alors Rij = ∅
Step 2 - Résolvez ces équations pour obtenir l'équation de l'état final en termes de Rij
Problem
Construire une expression régulière correspondant aux automates donnés ci-dessous -
Solution -
Ici, l'état initial et l'état final sont q1.
Les équations pour les trois états q1, q2 et q3 sont les suivantes -
q 1 = q 1 a + q 3 a + ε (ε move est parce que q1 est l'état initial0
q 2 = q 1 b + q 2 b + q 3 b
q 3 = q 2 a
Maintenant, nous allons résoudre ces trois équations -
q 2 = q 1 b + q 2 b + q 3 b
= q 1 b + q 2 b + (q 2 a) b (Valeur de substitution de q 3 )
= q 1 b + q 2 (b + ab)
= q 1 b (b + ab) * (Application du théorème d'Arden)
q 1 = q 1 a + q 3 a + ε
= q 1 a + q 2 aa + ε (Valeur de substitution de q 3 )
= q 1 a + q 1 b (b + ab *) aa + ε (valeur de remplacement de q 2 )
= q 1 (a + b (b + ab) * aa) + ε
= ε (a + b (b + ab) * aa) *
= (a + b (b + ab) * aa) *
Par conséquent, l'expression régulière est (a + b (b + ab) * aa) *.
Problem
Construire une expression régulière correspondant aux automates donnés ci-dessous -
Solution -
Ici, l'état initial est q 1 et l'état final est q 2
Maintenant, nous écrivons les équations -
q 1 = q 1 0 + ε
q 2 = q 1 1 + q 2 0
q 3 = q 2 1 + q 3 0 + q 3 1
Maintenant, nous allons résoudre ces trois équations -
q 1 = ε0 * [Comme, εR = R]
Donc, q 1 = 0 *
q 2 = 0 * 1 + q 2 0
Donc, q 2 = 0 * 1 (0) * [Par le théorème d'Arden]
Par conséquent, l'expression régulière est 0 * 10 *.