D'abord, trouver l'opération extérieure. Dans votre exemple, il s'agit de +. Lorsque vous avez un +, cela signifie que vous êtes en mesure d'accepter soit la chose à gauche, soit la chose à droite. Nous pouvons coder cela dans un NFA en utilisant vide (lambda, ou epsilon) transitions comme suit:
Q s Q'
q0 - M1
q0 - M2
Nous avons q0 comme point de départ et nous utilisons M1 et M2 pour représenter les machines qui acceptent les chaînes générées par le LHS et RHS, respectivement, de notre expression régulière. Quand nous disons q0 transitions à M1 et M2 sur lambda/epsilon - transitions vides - nous voulons dire que nous choisissons de façon non déterministe quel chemin descendre. La transition sera de q0 aux états initiaux de M1 et M2, quels que soient ces états.
Maintenant, nous répétons le processus récursivement sur chacun des LHS et RHS. Nous pouvons commencer avec le RHS car c'est plus simple. L'opération la plus externe est ici la concaténation (des symboles a et b). Concaténation est simple à représenter:
Q s Q'
q2 - M3
M3 - M4
Ici, q2 est l'état initial de M2 d'avant, et M3 et M4 représentent en tant-de-encore machines indéterminées qui acceptent LHS et RHS, respectivement, de la concaténation et b. Quand nous disons q2 transitions à M3, nous voulons dire qu'il passe à l'état initial M3; et quand nous disons M3 transitions à M4, nous entendons tous les états d'acceptation de M3 transition à l'état initial de M4.
En procédant récursivement, nous avons maintenant besoin de machines pour a et b. Ces deux ont la forme:
Q s Q'
q x q'
Où q est l'état initial, x est le symbole et q' est un état d'accepter.Nous obtenons donc:
Q s Q'
q3 b q4 (q3 initial, q4 accepting)
et
Q s Q'
q5 a q6 (q5 initial, q6 accepting)
Nous avons touché le fond de cette branche de récursivité et peut remonter jusqu'à, générer des entrées de béton dans la table de transition sur la base des machines concrètes que nous avons définies. Nous avons eu ceci:
Q s Q'
q2 - M3
M3 - M4
Et maintenant, nous savons ce que M3 et M4 ressemblent, afin que nous puissions remplacer:
Q s Q'
q2 - q3
q3 b q4
q4 - q5
q5 a q6 (q2 initial, q6 accepting)
Maintenant, nous sommes prêts à faire le LHS de l'opération +. L'opération la plus extérieure est *. La façon dont nous traitons ces derniers dans NFA est la suivante:
Q s Q'
q7 - M5
M5 - M5
Nous considérons maintenant l'opération suivante, concaténation. Nous avons déjà couvert cela et nous savons que nous obtenons ceci:
Q s Q'
q8 - M6
M6 - M7
Maintenant, nous avons besoin a et b. Encore une fois, nous savons que ceux-ci ressemblent:
Q s Q'
q9 a q10
et
Q s Q'
q11 b q12
Nous avons mis de nouveau ensemble:
Q s Q'
q8 - q9
q9 a q10
q10 - q11
q11 b q12 (q8 initial, q12 accepting)
Ensuite, nous faisons l'étoile Kleene:
Q s Q'
q7 - q8
q8 - q9
q9 a q10
q10 - q11
q11 b q12
q12 - q8 (q8 initial, q8 and q12 accepting)
Enfin, nous combinons toutes les règles dans un grand trans Table de correspondance:
Q s Q'
q0 - q2
q0 - q7
q2 - q3
q3 b q4
q4 - q5
q5 a q6
q7 - q8
q8 - q9
q9 a q10
q10 - q11
q11 b q12
q12 - q8 (q0 initial, q6, q8 and q12 accepting)
Ainsi, vous pouvez construire récursivement un NFA pour n'importe quelle expression régulière. Le NFA résultant aura des états inutiles dans le cas général mais l'optimisation NFA est un sujet délicat. Vous pouvez toujours prendre cette (ou n'importe quelle) NFA, la convertir en DFA en utilisant un algorithme connu et ensuite minimiser en utilisant un algorithme connu. Ensuite, vous avez un DFA minime, bien que cela puisse être beaucoup plus grand que même cette NFA rembourrée!
https://swtch.com/~rsc/regexp/ – rici