Conversion NDFA vers DFA

Énoncé du problème

Laisser X = (Q_x, ∑, δ_x, q₀, F_x)être un NDFA qui accepte le langage L (X). Nous devons concevoir un DFA équivalentY = (Q_y, ∑, δ_y, q₀, F_y) 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 ₀ , Q ₁ , ..., 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: