Construction de Thompson

L’algorithme de Thompson permet de construire un automate non-déterministe avec epsilon-transition à partir d’une expression régulière. L’automate se construit récursivement à partir de motifs de base :

Les éléments unitaires comme ∅, ε et a sont reconnus par

langage15

On considère les opérateurs de l’expression régulière R selon l’ordre d’extériorité décroissant. L’opérateur le plus extérieur permet de découper R en R1 | R2 , R1.R2 ou R1*  qui sont reconnus par

langage16

Voici un exemple de construction avec l’expression (a|b)(a∗|ba∗|b∗)∗

On commence la récursion par la création de (A)(B) – le contenu n’est qu’à titre indicatif, nous verrons comment remplir A et B au fur et à mesure.

langage17

Puis par la mise en place de l’étoile sur (B)* – ici on en profite pour faire le fonction OU dans (A) = (a|b).

langage18

La prochaine étape consiste à faire la fonction OU dans (B)=(C|D|E)

langage19

Le processus contenu en descendant récursivement jusqu’à l’obtention de l’automate de Thompson final.

langage20

Ce dernier devra alors être déterminisé et minimiser pour une meilleur lecture.

 

 

Publicités