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 })}
|
1 2 3 4 5 6 7 |
let rec eps_in e = match e with | Eps -> true | L a -> false | Etoile e' -> true | Plus (e', e'') -> (eps_in e') || (eps_in e'') | Mult (e', e'') -> (eps_in e') && (eps_in e'') val eps_in : exprat -> bool = <fun> |
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres