Calcul des préfixes, des suffixes, et des facteurs de taille 2

Si {\mathtt{e},\mathtt{e}^{\prime },\mathtt{e}^{\prime \prime }} sont des expressions rationnelles, on écrit {L,L^{\prime },L^{\prime \prime }} le langage qu’elles dénotent.

On peut calculer, par induction sur e, les ensembles {P(}préfixes de L{),S(}suffixes de L) et {F(}facteurs de degré 2 autorisés).

On utilisera le type exprat défini antérieurement.

On sera aussi amené à utiliser les fonctions union et produit vues précédemment.

{\vartriangleright} Une première fonction booléenne eps_in est nécessaire, qui renvoie true si le mot vide {\epsilon} fait partie de L.

Cette fonction repose sur les observations évidentes suivantes :

  • si e {=\epsilon ,} alors L {=\left\{\epsilon \right\},} donc L contient le mot vide {\epsilon !}
  • si e {=a,} alors L {=\left\{a\right\}} n{e_{\prime }} c{\star}ontient pas le mot vide !
  • si e {=(\mathtt{e}^{\prime })^{\star},} alors L = (L ) contient les {(L^{\prime })^{n},n\ge 0,} donc contient {(L^{\prime })^{0}=\left\{\epsilon \right\}}
  • si e {=\mathtt{e}^{\prime }+\mathtt{e}^{\prime \prime },} alors L = L + L , donc {\epsilon \in L\Leftrightarrow (\epsilon \in L^{\prime })} ou {(\epsilon \in L^{\prime \prime })} {\prime} {\prime \prime}
  • si e {=\mathtt{e}^{\prime }\mathtt{e}^{\prime \prime },} alors L {=L^{\prime }\cdot L^{\prime \prime },} donc {\epsilon \in L\Leftrightarrow (\epsilon \in L^{\prime })} et {(\epsilon \in L^{\prime \prime })}

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :