Minimisation DFA

Minimisation DFA à l'aide du théorème Myphill-Nerode

Algorithme

Input - DFA

Output - DFA réduit

Step 1- Tracez un tableau pour toutes les paires d'états (Q i , Q j ) pas nécessairement connectés directement [Tous ne sont pas marqués initialement]

Step 2- Considérez chaque paire d'états (Q i , Q j ) dans le DFA où Q i ∈ F et Q j ∉ F ou vice versa et marquez-les. [Ici F est l'ensemble des états finaux]

Step 3 - Répétez cette étape jusqu'à ce que nous ne puissions plus marquer d'états -

S'il y a une paire non marquée (Q i , Q j ), marquez-la si la paire {δ (Q i , A), δ (Q i , A)} est marquée pour un alphabet d'entrée.

Step 4- Combinez toutes les paires non marquées (Q i , Q j ) et faites-en un seul état dans le DFA réduit.

Exemple

Utilisons l'algorithme 2 pour minimiser le DFA indiqué ci-dessous.

Step 1 - Nous dessinons un tableau pour toutes les paires d'états.

une b c ré e F
une
b
c
ré
e
F

Step 2 - Nous marquons les paires d'états.

une b c ré e F
une
b
c ✔ ✔
ré ✔ ✔
e ✔ ✔
F ✔ ✔ ✔

Step 3- Nous allons essayer de marquer les paires d'états, avec une coche de couleur verte, de manière transitoire. Si nous entrons 1 pour l'état «a» et «f», il passera respectivement à l'état «c» et «f». (c, f) est déjà marqué, donc nous marquerons la paire (a, f). Maintenant, nous entrons 1 pour indiquer «b» et «f»; il ira à l'état «d» et «f» respectivement. (d, f) est déjà marqué, donc nous marquerons la paire (b, f).

une b c ré e F
une
b
c ✔ ✔
ré ✔ ✔
e ✔ ✔
F ✔ ✔ ✔ ✔ ✔

Après l'étape 3, nous avons des combinaisons d'états {a, b} {c, d} {c, e} {d, e} qui ne sont pas marquées.

On peut recombiner {c, d} {c, e} {d, e} en {c, d, e}

Par conséquent, nous avons deux états combinés comme - {a, b} et {c, d, e}

Ainsi, le DFA réduit final contiendra trois états {f}, {a, b} et {c, d, e}

Minimisation DFA à l'aide du théorème d'équivalence

Si X et Y sont deux états dans un DFA, nous pouvons combiner ces deux états en {X, Y} s'ils ne sont pas distinguables. Deux états peuvent être distingués, s'il y a au moins une chaîne S, de telle sorte que l'un de δ (X, S) et δ (Y, S) accepte et un autre n'accepte pas. Par conséquent, un DFA est minimal si et seulement si tous les états sont distinguables.

Algorithme 3

Step 1 - Tous les états Q sont divisés en deux partitions - final states et non-final states et sont désignés par P0. Tous les états d'une partition sont le 0 e équivalent. Prenez un compteurk et initialisez-le avec 0.

Step 2- Incrémenter k de 1. Pour chaque partition de P k , diviser les états de P k en deux partitions s'ils sont k-distinguables. Deux états au sein de cette partition X et Y sont k-distinguables s'il y a une entréeS tel que δ(X, S) et δ(Y, S) sont (k-1) -distinguables.

Step 3- Si P k ≠ P k-1 , répétez l'étape 2, sinon passez à l'étape 4.

Step 4- Combinez les k èmes ensembles équivalents et faites-en les nouveaux états du DFA réduit.

Exemple

Considérons le DFA suivant -

q δ (q, 0) δ (q, 1)
une b c
b une ré
c e F
ré e F
e e F
F F F

Appliquons l'algorithme ci-dessus au DFA ci-dessus -

  • P 0 = {(c, d, e), (a, b, f)}
  • P 1 = {(c, d, e), (a, b), (f)}
  • P 2 = {(c, d, e), (a, b), (f)}

Par conséquent, P 1 = P 2 .

Il existe trois états dans le DFA réduit. Le DFA réduit est le suivant -

Q δ (q, 0) δ (q, 1)
(un B) (un B) (c, d, e)
(c, d, e) (c, d, e) (F)
(F) (F) (F)