Berry-Sethi sur une expression

1. Linéarisation. On numérote les cinq occurrences de lettres :

$$(a_1|b_2{)}^{\ast }{a}_3{b}_4{b}_5.$$

2. Les trois ensembles. On les calcule par induction sur l'expression. Comme $(a_1|b_2{)}^{\ast }$ contient $\epsilon$, les premières lettres du produit sont celles de l'étoile et celles de $a_3{b}_4{b}_5$ :

$$P=\{a_1,b_2,a_3\},D=\{b_5\},$$

$$F=\{a_1{a}_1,a_1{b}_2,a_1{a}_3,b_2{a}_1,b_2{b}_2,b_2{a}_3,a_3{b}_4,b_4{b}_5\}.$$

Les six premiers facteurs viennent de l'étoile et de sa jonction avec $a_3$ ; les deux derniers, du suffixe $a_3{b}_4{b}_5$. Il y en a huit.

3. L'automate. Un état par lettre numérotée, plus l'état initial $i$ : six états. On va de $x$ vers $y$ en lisant la lettre de $y$ dès que $xy\in F$ ; l'initial mène à chaque lettre de $P$ ; l'unique acceptant est $b_5$.

4. Il n'est pas déterministe : depuis $i$, la lettre a mène à la fois vers $a_1$ et vers $a_3$ ; de même depuis $a_1$ et depuis $b_2$. C'est normal : Berry-Sethi produit un automate sans transition spontanée, ce qui est déjà beaucoup, mais pas déterministe.

Les chiffres mesurés. L'automate a bien $5+1=6$ états et $3+8=11$ transitions. Il a été exécuté sur les $4095$ mots de longueur au plus $11$ et comparé, mot par mot, à l'expression $(a|b{)}^{\ast }abb$ évaluée par dérivées de Brzozowski : accord complet. Déterminisé, il tombe à $5$ états ; minimisé, à $4$.