Conversion NDFA vers DFA
Énoncé du problème
Laisser X = (Qx, ∑, δx, q0, Fx)être un NDFA qui accepte le langage L (X). Nous devons concevoir un DFA équivalentY = (Qy, ∑, δy, q0, Fy) tel que L(Y) = L(X). La procédure suivante convertit le NDFA en son équivalent DFA -
Algorithme
Input - Un NDFA
Output - Un DFA équivalent
Step 1 - Créer une table d'état à partir du NDFA donné.
Step 2 - Créez un tableau d'état vide sous les alphabets d'entrée possibles pour le DFA équivalent.
Step 3 - Marquez l'état de départ du DFA par q0 (identique au NDFA).
Step 4- Découvrez la combinaison des états {Q 0 , Q 1 , ..., Q n } pour chaque alphabet d'entrée possible.
Step 5 - Chaque fois que nous générons un nouvel état DFA sous les colonnes de l'alphabet d'entrée, nous devons appliquer à nouveau l'étape 4, sinon passez à l'étape 6.
Step 6 - Les états qui contiennent l'un des états finaux du NDFA sont les états finaux du DFA équivalent.
Exemple
Considérons le NDFA montré dans la figure ci-dessous.
q | δ (q, 0) | δ (q, 1) |
---|---|---|
une | {a, b, c, d, e} | {d, e} |
b | {c} | {e} |
c | ∅ | {b} |
ré | {e} | ∅ |
e | ∅ | ∅ |
En utilisant l'algorithme ci-dessus, nous trouvons son équivalent DFA. Le tableau des états du DFA est présenté ci-dessous.
q | δ (q, 0) | δ (q, 1) |
---|---|---|
[une] | [a, b, c, d, e] | [d, e] |
[a, b, c, d, e] | [a, b, c, d, e] | [b, d, e] |
[d, e] | [e] | ∅ |
[b, d, e] | [c, e] | [e] |
[e] | ∅ | ∅ |
[c, e] | ∅ | [b] |
[b] | [c] | [e] |
[c] | ∅ | [b] |
Le diagramme d'état du DFA est le suivant: