L'algorithme contruit un automate non-déterministe acceptant l'ensemble des mots décrit par une expression rationnelle. Le nombre d'états de l'automate esr proportionnelle à la taille de l'expression.
Les grandes étapes de l'algorithme partant d'une expression rationnelle E sont les suivantes.
La première étape de l'algorithme consiste à rendre toutes les lettres distinctes dans l'expression. Chaque occurrence d'une même lettre est numérotée. L'expression E = (ab + b)* devient, par exemple, E' = (ab0 + b1)*.
Pour chaque langage L, on introduit ε(L), Fst(L), Lst(L) et Nxt(L) définis par les formules ci-dessous. L'ensemble ε(L) contient le mot vide ε si ce-dernier appartient à L ou rien sinon. Fst(L) et Lst(L) sont respectivement les ensembles de lettres qui apparaissent au début ou à la fin des mots de L. L'ensemble Nxt(L) est l'ensemble des paires de lettres (a,b) telles que ab est facteur d'au moins un mot de L.
ε(L) = {ε} ∩ L
Fst(L) = { a : aA* ∩ L ≠ ∅ }
Lst(L) = { a : A*a ∩ L ≠ ∅ }
Nxt(L) = { (a,b) : A*abA* ∩ L ≠ ∅ }
Les formules suivantes permettent de calculer récursivement les ensembles ε(L), Fst(L), Lst(L) et Nxt(L).
| ε(∅) = ∅ | Fst(∅) = ∅ | Nxt(∅) = ∅ |
| ε(ε) = {ε} | Fst(ε) = ∅ | Nxt(ε) = ∅ |
| ε(a) = ∅ | Fst(a) = {a} | Nxt(a) = ∅ |
| ε(K+L) = ε(K) + ε(L) | Fst(K+L) = Fst(K) + Fst(L) | Nxt(K+L) = Nxt(K) + Nxt(L) |
| ε(KL) = ε(K)ε(L) | Fst(KL) = Fst(K) + ε(K)Fst(L) | Nxt(KL) = Nxt(K) + Nxt(L) + (Lst(K) × Fst(L)) |
| ε(L*) = {ε} | Fst(L*) = Fst(L) | Nxt(L*) = Nxt(L) + (Lst(L) × Fst(L)) |
Soit E une expression rationnelle où toutes les lettres sont différentes. On construit un automate A de la façon suivante.