1  Calculette

On modélise le processus d'évaluation d'une calculette de bureau par un automate. Les états de l'automate sont des quadruplets (n, x, ·, r) où :
n
représente le dernier calcul effectué ;
x
représente la dernière touche appuyée ;
·
représente le dernier opérateur actionné ;
r
représente la valeur affichée.
L'ensemble des touches de la calculette est l'ensemble de caractères suivants : 0 1 2 3 4 5 6 7 8 9 + - * / = Les caratères + - * / = sont appelés opérateurs, les caractères 0 1 2 3 4 5 6 7 8 9 sont appelés chiffres.

La fonction de transition est :
(n, x, ·, r) c' (n, c', ·, 10.r+c') si x et c' sont des chiffres
(n, x, ·, s) c' (n, c', ·, c') si c' est un chiffre, mais pas x
(n, x, ·, s) o' (n· r, o', o', n· r) si o' est un opérateur
  1. Définir un type etat pour représenter les états de l'automate et une valeur de ce type représentant l'état initial.
  2. Définir une fonction trans, de type etat -> char -> etat pour implanter la fonction de transition.
  3. Définir une fonction calc de type char list -> etat qui itére la fonction de transition sur la liste de caratères passée en argument en partant de l'état initial.

2  Arbres lexicaux

Pour la représentation de dictionnaires, on utilisera des arbres lexicaux (ou tries). 
type noeud_lex = Lettre of char * bool * arbre_lex 
and  arbre_lex = noeud_lex  list;;
type mot = string;;
La valeur booléenne du noeud_lex marque la fin d'un mot lorsqu'elle vaut true. Dans une telle structure, la suite de mots <<  fa, far, faux, frise, frit, frite >> est stockée de la façon suivante :

L'étoile (*) marque la fin d'un mot.
  1. Écrire la fonction existe existe qui teste si un mot appartient à un dictionnaire de type arbre_lex.

  2. Écrire une fonction ajoute ajouted qui prend un mot et un dictionnaire et retourne un nouveau dictionnaire qui contient ce mot en plus. Si le mot existe déjà, il n'est pas nécessaire de l'ajouter.

  3. Écrire une fonction construit construit qui prend une liste de mots et construit le dictionnaire correspondant.

  4. Écrire une fonction verifie filtre qui prend une liste de mots et un dictionnaire et retourne la liste des mots n'appartenant pas à ce dictionnaire.

  5. Écrire une fonction selecte selecte qui prend un dictionnaire et une longueur et retourne l'ensemble des mots de cette longueur.
This document was translated from LATEX by HEVEA.