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 P₀. 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.