Construction d'une FA à partir d'une ER
Nous pouvons utiliser la construction de Thompson pour trouver un automate fini à partir d'une expression régulière. Nous allons réduire l'expression régulière en plus petites expressions régulières et les convertir en NFA et enfin en DFA.
Certaines expressions RA de base sont les suivantes -
Case 1 - Pour une expression régulière 'a', on peut construire la FA suivante -
Case 2 - Pour une expression régulière 'ab', on peut construire la FA suivante -
Case 3 - Pour une expression régulière (a + b), on peut construire la FA suivante -
Case 4 - Pour une expression régulière (a + b) *, on peut construire le FA suivant -
Méthode
Step 1 Construisez un NFA avec des déplacements Null à partir de l'expression régulière donnée.
Step 2 Supprimez la transition Null du NFA et convertissez-la en son équivalent DFA.
Problem
Convertir le RA suivant en son équivalent DFA - 1 (0 + 1) * 0
Solution
Nous allons concaténer trois expressions "1", "(0 + 1) *" et "0"
Maintenant, nous allons supprimer le εtransitions. Après avoir retiré leε transitions de la NDFA, nous obtenons ce qui suit -
Il s'agit d'un NDFA correspondant au RE - 1 (0 + 1) * 0. Si vous souhaitez le convertir en DFA, appliquez simplement la méthode de conversion NDFA en DFA décrite au chapitre 1.
Automates finis avec déplacements nuls (NFA-ε)
Un automate fini avec des mouvements nuls (FA-ε) ne transite pas seulement après avoir donné une entrée à partir de l'ensemble d'alphabet, mais aussi sans aucun symbole d'entrée. Cette transition sans entrée est appelée unnull move.
Un NFA-ε est représenté formellement par un 5-tuple (Q, ∑, δ, q 0 , F), constitué de
Q - un ensemble fini d'états
∑ - un ensemble fini de symboles d'entrée
δ- une fonction de transition δ: Q × (∑ ∪ {ε}) → 2 Q
q0- un état initial q 0 ∈ Q
F - un ensemble d'états finaux de Q (F⊆Q).
Ce qui précède (FA-ε) accepte un ensemble de chaînes - {0, 1, 01}
Suppression des mouvements nuls des automates finis
Si dans un NDFA, il y a un déplacement move entre le sommet X et le sommet Y, nous pouvons le supprimer en utilisant les étapes suivantes -
- Trouvez tous les bords sortants de Y.
- Copiez tous ces bords à partir de X sans changer les étiquettes de bord.
- Si X est un état initial, faites de Y également un état initial.
- Si Y est un état final, faites de X également un état final.
Problem
Convertissez le NFA-ε suivant en NFA sans déplacement nul.
Solution
Step 1 -
Ici, la transition ε est entre q1 et q2, alors laisse q1 est X et qf est Y.
Ici, les fronts sortants de q f sont vers q f pour les entrées 0 et 1.
Step 2 -
Maintenant, nous allons copier toutes ces arêtes de q 1 sans changer les arêtes de q f et obtenir le FA suivant -
Step 3 -
Ici q 1 est un état initial, nous faisons donc de q f également un état initial.
Alors la FA devient -
Step 4 -
Ici q f est un état final, donc nous faisons de q 1 aussi un état final.
Alors la FA devient -
