TD 7

Pour chacune des parties de ce TD, on fournit un fichier de tests. On conseille fortement d'effectuer ces tests. Tant que vous n'avez pas répondu à toutes les questions d'une partie, pour effectuer vos tests, il faut commenter les lignes superflues.

Vous déposerez vos fichiers comme vous l'avez fait jusqu'ici. Vous pouvez déposer plusieurs fois, le dernier dépôt sera pris en compte. Vous pouvez déposer quand vous voulez ; l'énoncé donne des balises, qui ne sont là qu'à titre indicatif.

Le sujet décrit des notions d'algorithmique des mots. Un mot est une suite finie de lettres (on autorise la suite vide, c'est-à-dire constituée d'aucun élément). Ici, les lettres seront représentées par des caractères (char), et les mots par des listes chaînées de caractères. Par exemple, le mot ABAA sera codé par la liste

L'opération fondamentale sur les mots est la concaténation : le mot obtenu en concaténant un mot l et un mot m est donné par la suite des lettres formant l, suivie de celles formant m. Par exemple, si l est le mot AB et m est le mot CD, alors la concaténation de l et m est le mot ABCD. On note lm le mot obtenu en concaténant l et m.

Le but final est de manipuler des mots "modulo un ensemble donné de relations", en programmant un algorithme dû à Knuth et Bendix. Par exemple, sachant que A et B satisfont aux relations BAB=1, AAA=1 et BB=A, on veut pouvoir automatiquement en déduire que A=BB=1 (ici, 1 désigne le mot vide) ; en effet, BABBAB peut se réécrire d'une part sous la forme 1 en utilisant deux fois la première règle, d'autre part sous la forme A en utilisant la troisième, puis la seconde, puis la troisième règle. Généralement, les idées ci-dessous permettent (autant que possible) de répondre au problème du mot dans un groupe donné par générateurs et relations.

Outre les classes et fonctions demandées, vous pouvez rajouter tout ce qui vous semblera utile. Sauf contrordre, toutes les fonctions qu'on vous demande d'écrire vont dans la classe Mot qu'on va définir ci-dessous. Dans l'énoncé, on note les caractères qui forment les mots en majuscules ; les mots eux-mêmes sont désignés par des lettres minuscules.

Rappels et compléments.

Le caractère A est noté 'A'.
Si une fonction maFonction de type static a été écrite dans une classe MaClasse, vous pouvez l'appeler depuis une autre classe par MaClasse.maFonction(....)


Vous pouvez écrire plusieurs classes dans un même fichier.
L'énoncé est très long, car il faut de nombreuses étapes avant de
 parvenir à l'algorithme complet. Ne paniquez pas, et faites de votre mieux.




1. Préliminaires sur les mots

1.1 La classe Mot

Dans ce TD, on représente des chaînes de caractères par des listes
chaînées de char. Créez la classe Mot, 
et rajoutez-y
 
un constructeur Mot(char c, Mot m) qui place le 
 caractère c en tête du mot m,
une fonction static void afficher(Mot m),
 qui affiche le mot m,
une fonction static Mot concatener(Mot m, Mot l)
 qui renvoie le mot formé de la concaténation de m et
 l. Le mot m devra être recopié.
 
une fonction static boolean egaux(Mot m, Mot l)
  qui renvoie true si et seulement si les deux mots sont égaux.


Le fichier test.



1.2 Ordre sur les mots

Rappel : Soient m et l deux mots (non
vides). Pour comparer m et l pour l'ordre
lexicographique, on regarde leurs premières lettres, qu'on note
m1 et l1.  Si m1 est
strictement plus petite que l1, le plus petit mot pour
l'ordre lexicographique est m ; si l1 est
strictement plus petite que m1, le plus petit mot pour
l'ordre lexicographique est l. En cas d'égalité, on
regarde les secondes lettres, etc...



On dira dans la suite qu'un mot l est plus petit
qu'un mot m si l est de taille strictement
inférieure à celle de m, ou, en cas d'égalité, si
l vient strictement avant m pour l'ordre
lexicographique (cet ordre n'est donc pas l'ordre
lexicographique).



Exemple : BA est plus petit que BB,
qui est plus petit que ABA.



Écrire une fonction static int comparer(Mot l,
Mot m) qui renvoie -1 si et seulement si 
l est plus petit que m, 0 s'ils coïncident,
 et 1 si m est plus petit que l. Pour
 comparer des caractères, on peut utiliser <.



Le fichier test.



1.3 Sous-mots

On dit qu'un mot m est un sous-mot d'un mot
l s'il existe des mots a et b,
éventuellement vides, tels que l s'écrive
amb (c'est-à-dire a concaténé avec
m concaténé avec b). On cherche à écrire une fonction
estSousMot qui teste si c'est le cas et, si oui, renvoie
a et b.



Exemple : ABB est un sous-mot de AABBC.


Pour enregistrer simultanément un booléen et deux mots, on utilisera
  une classe BooleenMots. Créez cette classe, 
  munissez-la des champs et des constructeurs qui vont sembleront 
  utiles, et d'une méthode d'affichage static void
  afficher(BooleenMots b). 
Écrire une fonction static BooleenMots estSousMotGauche(Mot m, Mot 
  l), qui traite le cas particulier où l s'écrit 
  mb (c'est-à-dire où a est le mot vide).
Écrire la fonction static BooleenMots estSousMot(Mot m, Mot 
  l) ; il est conseillé d'utiliser la fonction précédente. 


Le fichier test.







2 Réécriture

2.1 Règles de réécriture

Une règle de réécriture est la donnée de deux mots
m et n, avec n plus petit
que m. On note r=(m,n).



Exemple : m=ABB et n=BA 
forment une règle de réécriture.


Créez une classe Regle, et munissez-la d'un
  constructeur Regle(Mot a, Mot b).  On ne supposera pas
  que a est plus petit que b ni
  l'inverse. Si a=b, on pourra lancer une erreur par
  throw new Error("Erreur: mots identiques.");




Étant donnés un mot l et une règle r=(m,n),
on peut utiliser r pour réécrire (on dira aussi réduire)
l si m est un sous-mot de l, de
sorte que l s'écrive smt. Le résultat de la
réécriture sera le mot snt. L'idée sous-jacente est
qu'une règle de réécriture code une relation entre des mots, et on
cherche à obtenir ce qu'on appelle un "forme normale" non réductible
modulo cette relation.



Exemple : La règle  (ABB,BA)  
 permet de réécrire AABBC en
 ABAC

Écrire la fonction static Mot remplacerUneFois(Regle r, Mot 
  l) qui effectue une telle réécriture, si c'est possible
  (si plusieurs réécritures différentes sont possibles, on 
   effectuera la première que l'on rencontrera). 
   Sinon, on renvoie null.



Le fichier test.



2.2 Ensembles de mots

Pour la suite, on a besoin d'une structure qui code des ensembles de
mots. On utilisera pour cela des listes de mots. 

Créez une classe ListeMots, et
  munissez-la des champs utiles, et d'un constructeur ListeMots(Mot m,
  ListeMots l). Les fonctions demandées ci-dessous 
  iront dans cette classe.
Écrire une fonction static void afficher(ListeMots e).
Écrire une fonction static boolean estPresent(Mot m, ListeMots
  e) qui indique si m est dans
  e.
Écrire une fonction static ListeMots union(ListeMots e, ListeMots
  f). On supposera que e et f sont 
  sans répétition ; cette fonction doit alors renvoyer une liste
  contenant la réunion des éléments de e et
  f, sans répétition.


Le fichier test.



2.3 Plusieurs règles de réécriture

On cherche maintenant à appliquer plusieurs règles de réécriture à un
mot. Pour prendre en compte le fait que le
résultat n'est pas unique, on va renvoyer un ensemble de mots.
On stocke les règles dans un tableau regles.  On rappelle
que les indices d'un tel tableau vont de 0 à
regles.length-1.


Écrivez une fonction static ListeMots reecrire(Regle r, Mot
   m) qui renvoie la liste (sans répétition) de tous les mots
   que l'on peut obtenir en une application de la règle r
   à m (remarquez la différence avec
   remplacerUneFois, qui n'effectue qu'une seule de ces
   réécritures).

  Exemple : si r=(AB,A) et m=ABBAB,
   cette fonction doit renvoyer la liste formée de ABAB
   et ABBA.

Écrivez une fonction static ListeMots reecrire(Regle[]
 regles, Mot m) qui tente d'appliquer chaque règle du tableau à 
  m et renvoie l'ensemble des 
  résultats (sans répétition). Si aucune réduction n'est possible, 
  on renvoie null.

Écrivez une fonction 
 static ListeMots reecrire(Regle[] regles, ListeMots e)
 qui tente d'appliquer toutes les règles du tableau à tous les mots de 
  e et renvoie l'ensemble des résultats (sans
 répétition). Si aucune réduction n'est possible, 
  on renvoie null.
Un mot est irréductible pour un ensemble de règles
  si aucune d'entre elles ne peut le réduire. 
Écrivez une fonction 
 static ListeMots irreductibles(Regle[] regles, ListeMots e)
 qui renvoie l'ensemble des mots de e
  irréductibles pour regles.



Le fichier test.




2.4 Applications itérées

Pour conclure cette partie, on cherche à obtenir tous les mots
irréductibles que l'on peut déduire à partir d'un mot m
de départ, et d'un système de règles.  L'algorithme commence avec un
ensemble e réduit au mot m. Ensuite, on
ajoute à e l'ensemble formé de tous les mots obtenus en
appliquant toutes les règles disponibles à tous les mots de
e ; on continue jusqu'à stabilisation, et on renvoie les
mots irréductibles de e.



Écrivez une fonction static ListeMots tousLesMots(Regle[]
 regles, Mot m) qui implante cet algorithme.



Le fichier test.







3. Complétion d'un ensemble de règles

Pour rendre le résultat de la réduction unique, on va introduire de
nouvelles règles. 

3.1 Adjonction de règles, premier cas



Pour commencer, on considère deux règles q=(l,u) et
r=(m,v), et on fait l'hypothèse que m est un
sous-mot de l, de sorte que l s'écrit 
smt. Ce mot peut donc se réécrire par q
sous la forme u, et par r sous la forme
svt. 

Si u est différent de svt, on formera la
règle composée de ces deux mots.

Écrire une fonction static
  Regle nouvelleRegle1(Regle q,
  Regle r) qui renvoie cette nouvelle règle, ou
  null.



Le fichier test.



3.2 Adjonction de règles, second cas

On dit maintenant qu'un couple de mots (l,m) a un
PGCD non trivial s'il existe un mot n
non vide et des mots s, t tels que
l s'écrive sn et que m
s'écrive nt. Remarquez que n n'est pas 
nécessairement unique.



On considère ensuite deux règles q=(l,u) et
r=(m,v). Si l et m ont un
PGCD non trivial, le mot snt peut être réduit par
q en ut, et par r en
sv.  Si ut est différent de sv,
il y a conflit. On va alors rajouter à notre stock de règles la règle
formée par ut et sv.


Écrire une fonction static Regle nouvelleRegle2(Regle q,
  Regle r) qui renvoie cette nouvelle règle, ou
  null.



Le fichier test.



3.3 Complétion

Pour conclure, on décrit comment compléter un ensemble de règles
e. On applique nouvelleRegle1 et
nouvelleRegle2 à chaque couple de règles de
e. Ceci produit (éventuellement) de nouvelles règles. On
réduit alors les membres de gauche et de droite de chacune de ces
nouvelles règles par e. Si le résultat de chaque
réduction est trivial (les membres de gauche et de droite se réduisent
en le même mot), on a terminé. Sinon, on rajoute les règles
réduites à e, et on recommence.


Écrire une fonction static Regle[] completion(Regle[]
 e) qui effectue cette complétion.