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}
{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: