Définition Une expression rationnelle sur un alphabet {\Sigma} est dite linéaire si chaque lettre de {\Sigma} y apparaît au plus une fois.
Par exemple, l’expression rationnelle {\epsilon +a(b^{\star}+c)} est linéaire, mais pas {aa^{\star}.}
La fonction suivante, baptisée alph_exprat, renvoie l’alphabet associé à une expression rationnelle, et plus précisément la liste (triée mais sans suppression des doublons) des lettres qui apparaissent dans cette expression :
|
1 2 3 4 5 6 7 8 9 10 11 |
let alph_exprat e = (* calculer l'alphabet d'une expression rationnelle *) let lm = ref [] (* cette liste contiendra l'alphabet *) in let rec aux e = match e with (* linéarisation de e par induction *) | Eps -> () (* expression vide, on ne fait rien *) | Plus (e', e'') -> aux e'; aux e'' (* scanne récursivement les composantes *) | Mult (e', e'') -> aux e'; aux e'' (* idem *) | Etoile e' -> aux e' (* idem pour l'étoile *) | L a -> lm := a :: !lm; (* ajoute la lettre à l'alphabet *) in aux e; (* recherche l'alphabet de e *) List.sort compare !lm;; (* renvoie alphabet trié de l'expression *) val alph_exprat : exprat -> string list = <fun> |
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres