package GenRGenS.ratexpr;
import java.util.*;
import java.io.*;

/** La classe Automate implemente un automate au sens mathematiques
 *  (_etats, _alphabet, _etatsInitiaux, _etatsTerminaux, _transitions). 
 *  On peut construire un automate a partir d'une expression rationnelle 
 *  (interface RatExpr) et les deux fonctions principales proposées sont la 
 *  determinisation et la minimisation de l'automate. Un etat est caracterise 
 *  par son numero; en particulier, deux etats differents ne peuvent pas avoir 
 *  le meme numero.*/
class Automate {
	//designe le premier numero d'etat libre superieur au plus grand des numeros
	//des autres etats.
	private int _numEtatLibre; 
	
	private Set _alphabet;
	
	private HashMap _etats;
	private HashSet _etatsInitiaux;
	private HashSet _etatsTerminaux;
	
	//_transitions.get(depart).get(etiq) == Ensemble
	// des etats d'arrivée de la transition depart-etiq->arrivee
	private HashMap _transitions;
	//(_deterministe==true) => l'automate est deterministe.
	private boolean _deterministe = false;
	//(_minimal==true) => l'automate est minimal.
	private boolean _minimal = false;

	
	/**Constructeur par defaut: A=({0}, {}, {0}, {0}, {}).
	A est donc deterministe et minimal.*/
	public Automate() {
		_numEtatLibre = 0;
		_alphabet = new HashSet();
		_etats = new HashMap();
		_etatsInitiaux = new HashSet();
		_etatsTerminaux = new HashSet();
		_transitions = new HashMap();
		
		Etat e = new Etat(_numEtatLibre,true,false);
		_etats.put(e.getNum(),e);
		_etatsInitiaux.add(e);
		
		_numEtatLibre++;
		_deterministe = true;
		_minimal = true;
	}
	
	/**Constructeur à partir d'un etat: A=({e},
	                                       {},
	                                       {e},
	                                       {e} si e est terminal {} sinon,
	                                       {}).
	A est donc deterministe et minimal.*/
	public Automate(Etat e) {
		//On impose qu'un automate ait toujours au moins un état initial
		e.setInitial(true);
		_numEtatLibre = e.getNum().intValue()+1;
		_alphabet = new HashSet();
		_etats = new HashMap();
		_etatsInitiaux = new HashSet();
		_etatsTerminaux = new HashSet();
		_transitions = new HashMap();
		
		_etats.put(e.getNum(),e);
		_etatsInitiaux.add(e);
		if (e.isTerminal())
			_etatsTerminaux.add(e);
		
		_deterministe = true;
		_minimal = true;
	}

	/**Constructeur par passage d'attributs. On affecte chaque attribut a la
	 * valeur passe en argument.*/
	public Automate(int numEtatLibre,Set alphabet,HashMap etats,
					HashSet etatsInitiaux,HashSet etatsTerminaux,
					HashMap transitions,boolean deterministe,boolean minimal) {
		_numEtatLibre = numEtatLibre;
		_alphabet = alphabet;
		_etats = etats;
		_etatsInitiaux = etatsInitiaux;
		_etatsTerminaux = etatsTerminaux;
		_transitions = transitions;
		
		_deterministe = deterministe;
		_minimal = minimal;
	}
	
	/**Constructeur par copie : On cree un automate identique a celui passe en
	 * argument.*/
	public Automate(Automate a) {
		_numEtatLibre = a.getNumEtatLibre();
		_alphabet = new HashSet(a.getAlphabet());
		_etats = new HashMap(a.getEtats());
		_etatsInitiaux = new HashSet(a.getEtatsInitiaux());
		_etatsTerminaux = new HashSet(a.getEtatsTerminaux());
		_transitions = new HashMap(a.getTransitions());
		
		_deterministe = a.isDeterministe();
		_minimal = a.isMinimal();
	}
	
	/**Constructeur d'apres une expression rationnelle : On utilise un
	 * algorithme de traduction d'une expression rationnelle en automate non
	 * deterministe.*/
	public Automate(RatExpr expr) {
		this(expr,0);
	}
	
	//Constructeur identique au precedent, on precise juste l'indice dep a
	//partir duquel on veut numeroter les etats.
	private Automate(RatExpr expr,int dep) {
		
		_numEtatLibre = dep;
		_alphabet = new HashSet();
		_etats = new HashMap();
		_etatsInitiaux = new HashSet();
		_etatsTerminaux = new HashSet();
		_transitions = new HashMap();
		
		//Cas de base
		if (expr == null) {  //expr = vide => A=({dep}, {}, {dep}, {}, {})
			Etat e = new Etat(_numEtatLibre,true,false);
			_numEtatLibre++;
			_etats.put(e.getNum(),e);
			_etatsInitiaux.add(e);
			_deterministe = true;
			_minimal = true;
		}
		else
		
		if (expr instanceof RatExprTerm) {
			RatExprTerm terme = (RatExprTerm) expr;
			
			//expr = Epsilon => A=({dep}, {}, {dep}, {dep}, {})
			if (terme.isEpsilon()) {

				Etat e = new Etat(_numEtatLibre,true,true);
				_numEtatLibre++;
				_etats.put(e.getNum(),e);
				_etatsInitiaux.add(e);
				_etatsTerminaux.add(e);
				_deterministe = true;
				_minimal = true;
			}
			//expr = a =>
			//   A=({dep, dep+1}, {a}, {dep}, {dep+1}, { (dep-a->(dep+1)) })
			else {
				Etat ei = new Etat(_numEtatLibre,true,false);
				_numEtatLibre++;
				_etats.put(ei.getNum(),ei);
				_etatsInitiaux.add(ei);
				
				Etat et = new Etat(_numEtatLibre,false,true);
				_numEtatLibre++;
				_etats.put(et.getNum(),et);
				_etatsTerminaux.add(et);
				
				ajoutTransition(ei,terme.getCharacter(),et);
				
				_deterministe = true;
				_minimal = true;
			}
		}
		
		//Cas d'induction
		else
		
		if (expr instanceof RatExprPlus) { 
			//expr = E+ et Automate(E)=(EEtats , EAlphabet, EInitiaux,
			//ETerminaux, ETransitions)
	        //=> A(expr)=(EEtats,
			//            EAlphabet,
			//            EInitiaux,
			//            ETerminaux,
			//            ETransitions
			//          U { (t-eps->i | t appartient a ETerminaux et i
			//                          appartient a EItiniaux})

			RatExprPlus ePlus = (RatExprPlus) expr;
			
			Automate a = new Automate(ePlus.getExpression(),_numEtatLibre);
			_numEtatLibre = a.getNumEtatLibre();
			_alphabet.addAll(a.getAlphabet());
			_etats.putAll(a.getEtats());
			_etatsInitiaux.addAll(a.getEtatsInitiaux());
			_etatsTerminaux.addAll(a.getEtatsTerminaux());
			
			copieTransitions(a.getTransitions());
			for(Iterator it1 = _etatsInitiaux.iterator();it1.hasNext();) {
				Etat ei = (Etat) it1.next();
				
				for(Iterator it2 = _etatsTerminaux.iterator();it2.hasNext();) {
					Etat et = (Etat) it2.next();
					
					ajoutTransition(et,null,ei);
				}
			}
		}
		else
		
		if (expr instanceof RatExprEtoile) {
			//expr = E* et Automate(E)=(EEtats , EAlphabet, EInitiaux,
			//                           ETerminaux, ETransitions)
			//=> A(expr)=(EEtats,
			//            EAlphabet,
			//            EInitiaux,
			//            ETerminaux U EInitiaux,
			//            ETransitions U { (t-eps->i | t appartient a
			//                        ETerminaux et i appartient a EItiniaux})

			RatExprEtoile eEtoile = (RatExprEtoile) expr;
			
			Automate a = new Automate(eEtoile.getExpression(),_numEtatLibre);
			_numEtatLibre = a.getNumEtatLibre();
			_alphabet.addAll(a.getAlphabet());
			_etats.putAll(a.getEtats());
			_etatsInitiaux.addAll(a.getEtatsInitiaux());
			_etatsTerminaux.addAll(a.getEtatsTerminaux());
			
			copieTransitions(a.getTransitions());
			for(Iterator it1 = _etatsInitiaux.iterator();it1.hasNext();) {
				Etat ei = (Etat) it1.next();
				
				for(Iterator it2 = _etatsTerminaux.iterator();it2.hasNext();) {
					Etat et = (Etat) it2.next();
					
					ajoutTransition(et,null,ei);
				}
			}
			
			//modification des etats initiaux qui deviennent terminaux
			for(Iterator it = _etatsInitiaux.iterator();it.hasNext();) {
				Etat e = (Etat) it.next();
				
				_etatsTerminaux.add(e);
				e.setTerminal(true);
			}
		}
		else
		
		if (expr instanceof RatExprOu) {
			//expr = E1|E2 et Automate(E1)=(E1Etats , E1Alphabet, E1Initiaux,
			//                              E1Terminaux, E1Transitions)
			//             et Automate(E2)=(E2Etats , E2Alphabet, E2Initiaux,
			//                              E2Terminaux, E2Transitions)
			//=> A(expr)=(E1Etats U E2Eats U {i},
			//            E1Alphabet U E2Alphabet,
			//            {i},
			//            E1Terminaux U E2Terminaux,
			//            E1Transitions U E2Transitions
			//             U { (i-eps->anc_i | anc_i appartient a
			//                                 (E1Initiaux U E2Ititiaux) })

			RatExprOu eOu = (RatExprOu) expr;
			
			Automate a = new Automate(eOu.getLeft(),_numEtatLibre);
			_numEtatLibre = a.getNumEtatLibre();
			_alphabet.addAll(a.getAlphabet());
			_etats.putAll(a.getEtats());
			_etatsInitiaux.addAll(a.getEtatsInitiaux());
			_etatsTerminaux.addAll(a.getEtatsTerminaux());
			
			copieTransitions(a.getTransitions());
			
			Automate b = new Automate(eOu.getRight(),_numEtatLibre);
			_numEtatLibre = b.getNumEtatLibre();
			_alphabet.addAll(b.getAlphabet());
			_etats.putAll(b.getEtats());
			_etatsInitiaux.addAll(b.getEtatsInitiaux());
			_etatsTerminaux.addAll(b.getEtatsTerminaux());
			
			copieTransitions(b.getTransitions());
			
			Etat orig = new Etat(_numEtatLibre,false,false);
			_numEtatLibre++;
			_etats.put(orig.getNum(),orig);
			for(Iterator it = _etatsInitiaux.iterator();it.hasNext();) {
				Etat e = (Etat) it.next();

				e.setInitial(false);
				
				ajoutTransition(orig,null,e);
			}
			orig.setInitial(true);
			_etatsInitiaux.clear();
			_etatsInitiaux.add(orig);	
		}
		else
		
		if (expr instanceof RatExprPoint) {
			//expr = E1.E2 et Automate(E1)=(E1Etats , E1Alphabet, E1Initiaux,
			//                              E1Terminaux, E1Transitions)
			//             et Automate(E2)=(E2Etats , E2Alphabet, E2Initiaux,
			//                              E2Terminaux, E2Transitions)
			//=> A(expr)=(E1Etats U E2Eats,
			//            E1Alphabet U E2Alphabet,
			//            E1Initiaux,
			//			     E2Terminaux,
			//            E1Transitions
			//                U E2Transitions
			//                U { (t1-eps->i2 | t1 appartient a E1Terminaux
			//                               et i2 appartient a E2Ititiaux) })
			
			RatExprPoint ePoint = (RatExprPoint) expr;
			
			Automate a = new Automate(ePoint.getLeft(),_numEtatLibre);
			_numEtatLibre = a.getNumEtatLibre();
			_alphabet.addAll(a.getAlphabet());
			_etats.putAll(a.getEtats());
			_etatsInitiaux.addAll(a.getEtatsInitiaux());
			_etatsTerminaux.addAll(a.getEtatsTerminaux());
			
			copieTransitions(a.getTransitions());
			
			Automate b = new Automate(ePoint.getRight(),_numEtatLibre);
			_numEtatLibre = b.getNumEtatLibre();
			_alphabet.addAll(b.getAlphabet());
			_etats.putAll(b.getEtats());
			_etatsInitiaux.addAll(b.getEtatsInitiaux());
			_etatsTerminaux.addAll(b.getEtatsTerminaux());
			
			copieTransitions(b.getTransitions());
			
			for(Iterator it1=a.getEtatsTerminaux().iterator();it1.hasNext();){
				Etat et = (Etat) it1.next();

				et.setTerminal(false);
				_etatsTerminaux.remove(et);
				for(Iterator it2=b.getEtatsInitiaux().iterator();
				    it2.hasNext();) {
					Etat ei = (Etat) it2.next();
					
					ei.setInitial(false);
					_etatsInitiaux.remove(ei);
					
					ajoutTransition(et,null,ei);
				}
			}	
		}
		else
		
		if (expr instanceof RatExprPuiss) {
			//expr = E^n et pour tout 1<=i<=n
			//      Automate(Ei)=(EiEtats, EiAlphabet, EiInitiaux, EiTerminaux,
			//                    EiTransitions) = Automate(E)
			//=> A(expr)=(U EiEtats (1<=i<=n),
			//            E1Alphabet,
			//            E1Initiaux,
			//            EnTerminaux,
			//            (U EiTransitions (1<=i<=n))
			//                 U { (ti-eps->i(i+1)|
			//                           ti appartient a EiTerminaux
			//                        et i(i+1) appartient a E(i+1)Initiaux
			//                             pour tout 1<=i<=n })

 			RatExprPuiss ePuiss = (RatExprPuiss) expr;
			
			if (ePuiss.getPuissance() == 0) {
				Etat e = new Etat(_numEtatLibre,true,true);
				_numEtatLibre++;
				_etats.put(e.getNum(),e);
				_etatsInitiaux.add(e);
				_etatsTerminaux.add(e);
				_deterministe = true;
				_minimal = true;
				return;
			}
			
			Automate a = new Automate(ePuiss.getExpression(),_numEtatLibre);
			_numEtatLibre = a.getNumEtatLibre();
			_alphabet.addAll(a.getAlphabet());
			_etats.putAll(a.getEtats());
			_etatsInitiaux.addAll(a.getEtatsInitiaux());
			_etatsTerminaux.addAll(a.getEtatsTerminaux());
			
			copieTransitions(a.getTransitions());
			
			for(int i = ePuiss.getPuissance()-1;i>0;i--) {
				a = new Automate(ePuiss.getExpression(),_numEtatLibre);
				_numEtatLibre = a.getNumEtatLibre();
				_etats.putAll(a.getEtats());
				_etatsInitiaux.addAll(a.getEtatsInitiaux());
				
				copieTransitions(a.getTransitions());
				Collection initiauxASupprimer = new HashSet();
				Collection terminauxASupprimer = new HashSet();
				for(Iterator it1 = _etatsTerminaux.iterator();it1.hasNext();) {
					Etat et = (Etat) it1.next();
					
					et.setTerminal(false);
					terminauxASupprimer.add(et);
					for(Iterator it2 = a.getEtatsInitiaux().iterator();
					    it2.hasNext();) {
						Etat ei = (Etat) it2.next();
						
						ei.setInitial(false);
						initiauxASupprimer.add(ei);

						ajoutTransition(et,null,ei);
					}
				}
				_etatsTerminaux.addAll(a.getEtatsTerminaux());
				_etatsInitiaux.removeAll(initiauxASupprimer);
				_etatsTerminaux.removeAll(terminauxASupprimer);
			}
		}
		reduitEtatInitial();

	}

	/**reduit le nombre d'etats initiaux de l'automate a 1.*/
	private void reduitEtatInitial() {
		if (_etatsInitiaux.size()>1) {
			Etat depart = (Etat)_etats.get(new Integer(ajoutEtat(true, false)));
			for (Iterator it=_etatsInitiaux.iterator(); it.hasNext();) {
				Etat arrivee = (Etat)it.next();
				if (!depart.equals(arrivee)){
				  ajoutTransition(depart, null, arrivee);
				  arrivee.setInitial(false);
				}
			}
			_etatsInitiaux.clear();
			_etatsInitiaux.add(depart);
		}
	}


	/** Copie transitions dans l'attribut _transitions */
	private void copieTransitions(Map transitions) {
		HashMap tmp_etiq_arr = null;
		for(Iterator it = transitions.keySet().iterator(); it.hasNext(); ) {
			Object dep = it.next();
			tmp_etiq_arr = new HashMap();
			for(Iterator it2 = ((Map)transitions.get(dep)).keySet().iterator();
					it2.hasNext(); ) {
				Object etiq = it2.next();
				tmp_etiq_arr.put(etiq,
					new HashSet((Set)((Map)transitions.get(dep)).get(etiq)));
			}
			_transitions.put(dep,tmp_etiq_arr);
		}
	}
	
	/** Renvoie une copie de l'ensemble des transitions. */
	private HashMap getCopieTransitions() {
		HashMap res = new HashMap();
		HashMap tmp_etiq_arr = null;
		for(Iterator it = _transitions.keySet().iterator(); it.hasNext(); ) {
			Object dep = it.next();
			tmp_etiq_arr = new HashMap();
			for(Iterator it2 = ((Map)_transitions.get(dep)).keySet().iterator();
					it2.hasNext(); ) {
				Object etiq = it2.next();
				tmp_etiq_arr.put(etiq,
					new HashSet((Set)((Map)_transitions.get(dep)).get(etiq)));
			}
			res.put(dep,tmp_etiq_arr);
		}
		return res;
	}
	
	/**retourne la valeur de l'attribut _numEtatLibre.*/
	public int getNumEtatLibre() { return _numEtatLibre; }
	
	/**retourne la valeur de l'attribut _alphabet.*/
	public Set getAlphabet() { return _alphabet; }
	
	/**retourne la valeur de l'attribut _etats.*/
	public HashMap getEtats() { return _etats; }

	/**retourne la valeur de l'attribut _etatsInitiaux.*/
	public HashSet getEtatsInitiaux() { return _etatsInitiaux; }

	/**retourne la valeur de l'attribut _etatsTerminaux.*/
	public HashSet getEtatsTerminaux() { return _etatsTerminaux; }

	/**retourne la valeur de l'attribut _transitions.*/
	public HashMap getTransitions() { return _transitions; }

	/**retourne la valeur de l'attribut _deterministe.*/
	public boolean isDeterministe() { return _deterministe; }

	/**retourne la valeur de l'attribut _minimal.*/
	public boolean isMinimal() { return _minimal; }

	/**redefinission de la methode de conversion d'un automate vers une chaine
	 * de caractere.*/
	public String toString() {
		return "(alphabet = "+_alphabet.toString()+"\n etats = "
		     + _etats.values().size()+"\t "+_etats.toString()+"\n init = "
		     + _etatsInitiaux.toString()+"\n term = "
		     + _etatsTerminaux.toString()+"\n transitions = "
		     + _transitions.toString()+"\n)";
	}
	
	public boolean reconnait(Vector mot) {
		Set etatCourant = _etatsInitiaux, tmp = null;
			
		for(int i = 0; i < mot.size() ; i++) {
			Object etiq = mot.elementAt(i);
			tmp = successeurEnsemble(etatCourant,etiq);
			etatCourant = epsFermetureEnsemble(tmp);
		}
		
		for(Iterator it = etatCourant.iterator();it.hasNext();) {
			Etat e = (Etat) it.next();
			
			if (e.isTerminal() && _etatsTerminaux.contains(e))
				return true;
		}
		return false;
	}
	
	/** méthode permettant d'ajouter un état dans l'automate
	 *  @param initial vaut true si l'état créé est initial, false sinon
	 *  @param terminal vaut true si l'état créé est terminal, false sinon
	 *  @return renvoie le numéro de l'état créé
	 */
	public int ajoutEtat(boolean initial, boolean terminal) {
		Etat e = new Etat(_numEtatLibre,initial,terminal);
		_etats.put(e.getNum(),e);
		_numEtatLibre++;
		
		if (initial)
			_etatsInitiaux.add(e);
		
		if (terminal)
			_etatsTerminaux.add(e);
		
		_minimal = false;
		
		return e.getNum().intValue();
	}
	
	/** méthode qui permet d'ajouter une transition entre deux états existants
	 *  @param e1 représente le numéro de l'état de départ
	 *  @param etiquette est l'etiquette de la transition
	 *  @param e2 représente le numéro de l'état d'arrivée
	 *  @return true si et seulement si l'ajout s'est déroulé correctement
	 */
	public boolean ajoutTransition(int e1, Object etiquette, int e2) {
		Integer i1 = new Integer(e1);
		Integer i2 = new Integer(e2);
		if (_etats.containsKey(i1) && _etats.containsKey(i2)) {
			
			Etat etat1 = (Etat) (_etats.get(i1));
			Etat etat2 = (Etat) (_etats.get(i2));
			
			if (_transitions.containsKey(etat1)) {
				if (((Map)_transitions.get(etat1)).containsKey(etiquette))
					((Set) ((Map) _transitions.get(etat1)).get(etiquette))
					.add(etat2);
				else {
					Set etats_arrivee = new HashSet();
					etats_arrivee.add(etat2);
					((Map)_transitions.get(etat1)).put(etiquette,etats_arrivee);
				}
			}
			else {
				Map etiq_etat2 = new HashMap();
				Set etats_arrivee = new HashSet();
				etats_arrivee.add(etat2);
				etiq_etat2.put(etiquette,etats_arrivee);
				_transitions.put(etat1,etiq_etat2);
			}
			
			if (etiquette != null) {
				_alphabet.add(etiquette);
				
				if (((Set)((Map) _transitions.get(etat1)).get(etiquette)).size()
				    > 1)
					_deterministe = false;
			}
			else
				_deterministe = false;
			
			_minimal = false;
			
			return true;
		}
		return false;
	}
	
	/** méthode qui permet d'ajouter une transition entre deux états existants
	 *  @param e1 représente l'etat de départ
	 *  @param etiquette est l'etiquette de la transition
	 *  @param e2 représente l'état d'arrivée
	 *  @return true si et seulement si l'ajout s'est déroulé correctement
	 */
	public boolean ajoutTransition(Etat e1, Object etiquette, Etat e2) {
		return ajoutTransition(e1.getNum().intValue(),
		                       etiquette,
		                       e2.getNum().intValue());
	}
	
	/** méthode permettant de trouver les successeurs d'un état par une
	 *  transition donnée
	 *  @param orig représente le numero de l'état dont on veut les successeurs
	 *  @param etiq est l'étiquette de la transition
	 *  @return renvoie un Set des états accessibles de orig par une transition
	 *   d'étiquette etiq
	 */
	public Set successeur(int orig,Object etiq) {
		Integer origInteger = new Integer(orig);
		Set res = new HashSet();
		
		if (_etats.containsKey(origInteger)) {
			Etat origine = (Etat) (_etats.get(origInteger));
			
			if (_transitions.containsKey(origine))
				if (((Map) _transitions.get(origine)).containsKey(etiq))
					res = (Set) ((Map) _transitions.get(origine)).get(etiq);
		}
		
		return res;
	}
	
	/** méthode permettant de trouver les successeurs d'un état par une
	 *  transition donnée
	 *  @param orig représente l'état dont on veut les successeurs
	 *  @param etiq est l'étiquette de la transition
	 *  @return renvoie un Set des états accessibles de orig par une transition
	 *   d'étiquette etiq
	 */
	public Set successeur(Etat orig,Object etiq) {
		return successeur(orig.getNum().intValue(),etiq);
	}
	
	/** méthode permettant de trouver les successeurs d'un ensemble d'etats par
	 *  une transition donnée
	 *  @param origEnsemble représente l'ensemble des états dont on veut les
	 *   successeurs
	 *  @param etiq est l'étiquette de la transition
	 *  @return renvoie un Set des états accessibles de origEnsemble par une
	 *   transition d'étiquette etiq
	 */
	Set successeurEnsemble(Set origEnsemble,Object etiq) {
		Set res = new HashSet();
		
		for(Iterator it = origEnsemble.iterator();it.hasNext();) {
			Etat orig = (Etat) (it.next());
			int origNum = orig.getNum().intValue();
			
			res.addAll(successeur(origNum,etiq));
		}
		
		return res;
	}
	
	/** méthode permettant de calculer l'epsilon-fermeture d'un état
	 *  @param etat est le numéro de l'état dont on veut calculer la fermeture
	 *  @param res est l'ensemble dans lequel on calcule l'epsilon-fermeture
	 *   de etat
	 */
	private void epsFermeture(int etat,Set res) {
		Integer etatInteger = new Integer(etat);
		if (res ==null)
			res = new HashSet();
		
		if (_etats.containsKey(etatInteger)) {
			Etat e = (Etat) (_etats.get(etatInteger));
			res.add(e); //On oublie pas de rajouter e l'epsilon fermeture
			
			if (_transitions.containsKey(e))
				if (((Map) _transitions.get(e)).containsKey(null)) {
					Set epsFermeture_1coup = (Set) ((Map) _transitions.get(e))
					.get(null);
					epsFermetureEnsemble(epsFermeture_1coup,res);
				}
		}
	}
	
	/** méthode permettant de calculer l'epsilon-fermeture d'un état
	 *  @param etat est le numéro de l'état dont on veut calculer la fermeture
	 *  @return renvoie l'epsilon-fermeture de etat
	 */
	private Set epsFermeture(int etat) {
		Set res = new HashSet();
		epsFermeture(etat,res);
		return res;
	}
	
	private Set epsFermetureEnsemble(Set c, Set res) {
		if (res ==null)
			res = new HashSet();
		
		for(Iterator it = c.iterator(); it.hasNext();) {
			Etat e = (Etat) (it.next());
			
			if (!res.contains(e)) {
				int eNum = e.getNum().intValue();
				epsFermeture(eNum,res);
			}
		}
			
		return res;
	}
	
	private Set epsFermetureEnsemble(Set c) {
		Set res = new HashSet();
		if (c == null || c.isEmpty())
			return res;
		epsFermetureEnsemble(c,res);
		return res;
	}	
	
	/** méthode permettant de déterminiser l'automate
	 *  @return renvoie un automate déterministe reconnaissant le même langage
	 */
	public Automate determinise() {
		if (_deterministe)
			return new Automate(this);
		else {
		  try{
			int tmpNumEtatLibre=0;
			HashSet tmpAlphabet = new HashSet(_alphabet);
			HashMap tmpEtats = new HashMap();
			HashSet tmpEtatsInitiaux = new HashSet();
			HashSet tmpEtatsTerminaux = new HashSet();
			HashMap tmpTransitions = new HashMap();
			
			Stack pile = new Stack();
			Set etatCompose = epsFermetureEnsemble(_etatsInitiaux);
			EtatCompose EC = new EtatCompose(tmpNumEtatLibre,etatCompose);
			EC.setInitial(true);
			pile.push(EC);
			tmpNumEtatLibre++;
			tmpEtats.put(EC.getNum(),EC);
			tmpEtatsInitiaux.add(EC);
			if (EC.isTerminal())
				tmpEtatsTerminaux.add(EC);
			
			// represente l'ensemble des successeurs d'un etat composé pour
			// une etiquette donnée.
			Set successeurs;
			// represente l'ensemble des etats dans l'automate
			// non-deterministe correspondant a l'etat compose dans l'automate
			// deterministe.
			Set ensEtats;
			while (!pile.empty()) {
				EC = (EtatCompose) (pile.pop());
				ensEtats = new HashSet(); 
				
				//on calcule ensEtats pour l'etat compose courant EC.
				for(Iterator it3 = EC.getNumEtats().iterator();it3.hasNext();){ 
					Object num = it3.next();
				
					ensEtats.add(_etats.get(num));
				}
				
				//on calcule les transitions de l'etat composé EC.
				for(Iterator it1 = _alphabet.iterator();it1.hasNext();) {
					Object etiq = it1.next();
					
					//on calcule les successeurs de l'etat composé EC par
					// l'etiquette etiq.
					successeurs = successeurEnsemble(ensEtats,etiq);
					//on complete l'ensemble des successeurs en calculant
					//l'epsilon fermeture de cette ensemble.
					successeurs = epsFermetureEnsemble(successeurs);
					//s'il n'y a aucun successeur, on passe a l'etiquette
					//suivante.
					if (successeurs.isEmpty())
						continue;
					
					//ECtmp est l'etat composé de l'ensemble des successeurs
					//de EC.
					EtatCompose ECtmp = 
						new EtatCompose(tmpNumEtatLibre,successeurs);
					if (! ECtmp.equivaut(tmpEtats.values())) {
						//ECtmp est un nouvel etat
						
						//il faut donc le rajouter dans la pile d'etat a traiter
						pile.push(ECtmp);
						tmpNumEtatLibre++; 
						//on rajoute ECtmp dans l'ensemble des etats.
						tmpEtats.put(ECtmp.getNum(),ECtmp);

						if (ECtmp.isInitial())
							tmpEtatsInitiaux.add(ECtmp);

						if (ECtmp.isTerminal())
							tmpEtatsTerminaux.add(ECtmp);
						
						
						//Ajout d'une transtion dans tmpTransitions
						if (tmpTransitions.containsKey(EC)) {
							if (((Map)tmpTransitions.get(EC)).containsKey(etiq))
								((Set) ((Map) tmpTransitions.get(EC)).get(etiq))
								.add(ECtmp);
							else {
								Set etats_arrivee = new HashSet();
								etats_arrivee.add(ECtmp);
								((Map) tmpTransitions.get(EC))
								.put(etiq,etats_arrivee);
							}
						}
						else {
							Map etiq_ECtmp = new HashMap();
							Set etats_arrivee = new HashSet();
							etats_arrivee.add(ECtmp);
							etiq_ECtmp.put(etiq,etats_arrivee);
							tmpTransitions.put(EC,etiq_ECtmp);
						}
						
					}
					else {//ECtmp est un etat existant
						//On recupere l'etat existant correspondant a ECtmp.
						ECtmp = ECtmp.trouveEquivalent(tmpEtats.values());
						
						//Ajout d'une transtion dans tmpTransitions
						if (tmpTransitions.containsKey(EC)) {
							if (((Map)tmpTransitions.get(EC)).containsKey(etiq))
								((Set) ((Map) tmpTransitions.get(EC)).get(etiq))
								.add(ECtmp);
							else {
								Set etats_arrivee = new HashSet();
								etats_arrivee.add(ECtmp);
								((Map) tmpTransitions.get(EC))
								.put(etiq,etats_arrivee);
							}
						}
						else {
							Map etiq_ECtmp = new HashMap();
							Set etats_arrivee = new HashSet();
							etats_arrivee.add(ECtmp);
							etiq_ECtmp.put(etiq,etats_arrivee);
							tmpTransitions.put(EC,etiq_ECtmp);
						}
					}
				}
			}
			
			return new Automate(tmpNumEtatLibre,tmpAlphabet,tmpEtats,
			                    tmpEtatsInitiaux,tmpEtatsTerminaux,
			                    tmpTransitions,true,false);
   	  }catch(BadArgumentException ex) {return new Automate(this);}						
		}
	}
	
	/** méthode permettant de minimiser l'automate
	 *  @return renvoie un automate minimal reconnaissant le même langage que
	 *   l'automate courant
	 */
	public Automate minimise() {
		if (_minimal)
			return new Automate(this);
		else
			if (!_deterministe)
				return determinise().minimise();
			else {
			 
				int tmpNumEtatLibre=_numEtatLibre;
				HashSet tmpAlphabet = new HashSet(_alphabet);
				HashMap tmpEtats = new HashMap(_etats);
				HashSet tmpEtatsInitiaux = new HashSet(_etatsInitiaux);
				HashSet tmpEtatsTerminaux = new HashSet(_etatsTerminaux);
				HashMap tmpTransitions = getCopieTransitions();

				int taille = tmpEtats.size();
				//on construit un tableau d'équivalence entre les états de
				//l'automate
				boolean[][] equiv = new boolean[taille][taille];
				
				//On construit un tableau d'assocation entre l'indice dans une
				//ligne ou une colonne de equiv et l'état associé
				Map Int2Etat = new HashMap();
				Map Etat2Int = new HashMap();
				int i = 0;
				for(Iterator it = tmpEtats.values().iterator();it.hasNext();) {
					Etat e = (Etat) it.next();
					Integer ind = new Integer(i);
					Int2Etat.put(ind,e);
					Etat2Int.put(e,ind);
					i++;
				}
				
				//On initialise equiv en mettant à true tous les cases (p,q)
				// où p ou q est un état final
				//On ne se sert que de la partie supérieure du tableau
				int j = 0;
				Integer I,J;
				for(i = 0;i < taille;i++) {
					I = new Integer(i);
					Etat ei = (Etat) Int2Etat.get(I);
					
					for(j = i+1;j < taille;j++) {
						J = new Integer(j);
						Etat ej = (Etat) Int2Etat.get(J);
						equiv[i][j] = (ei.isTerminal() && !ej.isTerminal()) || 
									(!ei.isTerminal() && ej.isTerminal());
					}
				}
							
				//On modifie equiv jusqu'à ce qu'aucune case n'est changée
				//pendant une itération
				Object etiq = null;
				boolean aChanger = true;
				int indice = 0;
				while(aChanger) {
					aChanger = false;
					
					for(i = 0;i < taille;i++) {
						I = new Integer(i);
						Etat ei = (Etat) Int2Etat.get(I);
						
						for(j = i+1;j < taille;j++) {
							J = new Integer(j);
							Etat ej = (Etat) Int2Etat.get(J);
							
							if (!equiv[i][j]) {
								//aChangerBis vaut true quand la case courante
								//est changée, ainsi on ne fait pas toutes les
								//boucles
								boolean aChangerBis = false;
								for(Iterator it = tmpAlphabet.iterator();
								    it.hasNext() && !aChangerBis;) {
									etiq = it.next();
									indice++;
									//Comme l'automate est déterministe,
									//le résultat de successeur est soit vide
									//soit à un élément
									Set eiSuccEns = null;
									if (tmpTransitions.containsKey(ei))
										if (((Map) tmpTransitions.get(ei))
										     .containsKey(etiq))
											eiSuccEns = (Set) 
											  ((Map) tmpTransitions.get(ei))
											  .get(etiq);
									
									Set ejSuccEns = null;
									if (tmpTransitions.containsKey(ej))
										if (((Map) tmpTransitions.get(ej))
										    .containsKey(etiq))
											ejSuccEns = (Set)
											  ((Map) tmpTransitions.get(ej))
											  .get(etiq);
									
									if (eiSuccEns==null || ejSuccEns==null) {
										if (!(eiSuccEns == null
										   && ejSuccEns == null)) {
											equiv[i][j] = true;
											aChangerBis = true;
											aChanger = true;
										}
										continue;
									}
									
									Etat eiSucc = 
										(Etat) (eiSuccEns.toArray()[0]);
									Etat ejSucc =
										(Etat) (ejSuccEns.toArray()[0]);
	
									if (equiv[((Integer)Etat2Int.get(eiSucc))
											  .intValue()]
											 [((Integer)Etat2Int.get(ejSucc))
										      .intValue()]
									 || equiv[((Integer)Etat2Int.get(ejSucc))
									          .intValue()]
									  		 [((Integer)Etat2Int.get(eiSucc))
									  		  .intValue()]) {
										equiv[i][j] = true;
										aChangerBis = true;
										aChanger = true;
									}
								}
							}
						}
					}
				}

				//Les cases de equiv qui valent false désignent les états
				//équivalents. Il suffit donc de réunir les états équivalents
				//en 1 seul état. On construit un ensemble d'ensemble d'états
				//équivalents
				
				LinkedList equivalences = new LinkedList();
				Set s;
				boolean eiDansS,ejDansS,nouvEqui;
				for(i = 0;i < taille;i++) {
					I = new Integer(i);
					Etat ei = (Etat) Int2Etat.get(I);
					
					for(j = i+1;j < taille;j++) {
						J = new Integer(j);
						Etat ej = (Etat) Int2Etat.get(J);
						
						if (!equiv[i][j]) {
							nouvEqui = true;
							for(Iterator it = equivalences.iterator();
							    it.hasNext() && nouvEqui;) {
								s = (Set) it.next();
								eiDansS = s.contains(ei);
								ejDansS = s.contains(ej);
								
								if ( eiDansS || ejDansS) {
									nouvEqui = false;
									//On peut ajouter les 2 états car un Set
									//ne contient pas deux fois le même élément
									s.add(ei);
									s.add(ej);
								}
							}
							
							if (nouvEqui) {
								Set nouvelleEquivalence = new HashSet();
								nouvelleEquivalence.add(ei);
								nouvelleEquivalence.add(ej);
								if (!equivalences.add(nouvelleEquivalence))
									System.out.println("!!!!!!ERREUR!!!!!!\n"+
									                   "add(equivalence)");
							}
						}
					}
				}
				//On peut maintenant réduire le nombre d'états à l'aide des
				//équivalences
				boolean isTerminal,isInitial;
				Etat etatEqui,e;
				Set equivalence;

				for(Iterator it = equivalences.iterator();it.hasNext();) {
					equivalence = (Set) it.next();
					
					isInitial = false;
					isTerminal = false;
					etatEqui = null;
					for(Iterator it2 = equivalence.iterator();it2.hasNext();) {
						e = (Etat) it2.next();
						
						if (e.isInitial())
							isInitial = true;
						
						if (e.isTerminal())
							isTerminal = true;
						
						if (etatEqui == null)
							etatEqui = e;
						else {
							tmpEtats.remove(e.getNum());
							if (e.isInitial())
								tmpEtatsInitiaux.remove(e);
								
							if (e.isTerminal())
								tmpEtatsTerminaux.remove(e);
							
							//Mise à jour des transitions
							Map etiq_etats_etatEqui=(Map)tmpTransitions.get(e);
							if (etiq_etats_etatEqui == null) {
								etiq_etats_etatEqui = new HashMap();
								tmpTransitions.put(etatEqui,
												   etiq_etats_etatEqui);
							}
							
							if (tmpTransitions.containsKey(e)) {
								Map etiq_etats_e = (Map) tmpTransitions.get(e);
								
								for(Iterator it3 = etiq_etats_e.keySet()
								                   .iterator();
								    it3.hasNext();) {
									etiq = it3.next();
									
									if (etiq_etats_etatEqui.containsKey(etiq))
										((Set) etiq_etats_etatEqui.get(etiq))
										.addAll((Set) etiq_etats_e.get(etiq));
									else
										etiq_etats_etatEqui.put(etiq,
										         (Set) etiq_etats_e.get(etiq));
								}
								tmpTransitions.remove(e);
							}
							
							
							/* METTRE A JOUR
							 * etat-etiq->e    en     etat-etiq->etatEqui
							 */
							
							for(Iterator it4 = tmpTransitions.keySet()
							                     .iterator();
							    it4.hasNext();) {
								Etat depart = (Etat) it4.next();
								Map etiq_arrivee =
									(Map) tmpTransitions.get(depart);
								for(Iterator it5 = etiq_arrivee.keySet()
								                   .iterator();
								    it5.hasNext();) {
									etiq = it5.next();
									Set arrivee = (Set) etiq_arrivee.get(etiq);
									if (arrivee.contains(e)) {
										arrivee.remove(e);
										arrivee.add(etatEqui);
									}
								}
							}
						}
					}
					if (isInitial) {
						etatEqui.setInitial(isInitial);
						tmpEtatsInitiaux.add(etatEqui);
					}
					
					if (isTerminal) {
						etatEqui.setTerminal(isTerminal);
						tmpEtatsTerminaux.add(etatEqui);
					}
				}
				
				Automate res = 
					new Automate(tmpNumEtatLibre,tmpAlphabet,tmpEtats,
					             tmpEtatsInitiaux,tmpEtatsTerminaux,
					             tmpTransitions,true,true);
				res.gagneEspace();
				return res;
			 				
			}
		}
	
	/** Méthode utilisée uniquement aprè la minimisation pour optimiser la
	 *  taille des ensembles de l'automate */
	private void gagneEspace() {
	int tmpNumEtatLibre = 0;
	HashMap tmpEtats = new HashMap(_etats.size());
	for(Iterator it = _etats.keySet().iterator(); it.hasNext();) {
	    Integer numEtat = (Integer) it.next();
	    if (tmpNumEtatLibre <= numEtat.intValue()+1)
	    	tmpNumEtatLibre = numEtat.intValue()+1;
	    tmpEtats.put(numEtat,_etats.get(numEtat));
	}
	
	HashSet tmpEtatsInitiaux = new HashSet(_etatsInitiaux.size());
	for(Iterator it = _etatsInitiaux.iterator(); it.hasNext();)
	    tmpEtatsInitiaux.add(it.next());

	HashSet tmpEtatsTerminaux = new HashSet(_etatsTerminaux.size());
	for(Iterator it = _etatsTerminaux.iterator(); it.hasNext();)
	    tmpEtatsTerminaux.add(it.next());
	
	HashMap tmpTransitions = new HashMap(_transitions.size());
	for(Iterator it1 = _transitions.keySet().iterator(); it1.hasNext();) {
		Etat dep = (Etat) it1.next();
		Map etiq_arr = (Map) _transitions.get(dep);
		
		Map tmpEtiq_arr = new HashMap(etiq_arr.size());
		for(Iterator it2 = etiq_arr.keySet().iterator();it2.hasNext();) {
			Object etiq = it2.next();
			Set arr = (Set) etiq_arr.get(etiq);
			
			Set tmpArr = new HashSet(arr);
			for(Iterator it3 = arr.iterator(); it3.hasNext();)
				tmpArr.add(it3.next());
			
			tmpEtiq_arr.put(etiq,tmpArr);
		}
		
		tmpTransitions.put(dep,tmpEtiq_arr);
	}
	
	_numEtatLibre = tmpNumEtatLibre;
	_etats = tmpEtats;
	_etatsInitiaux = tmpEtatsInitiaux;
	_etatsTerminaux = tmpEtatsTerminaux;
	_transitions = tmpTransitions;
    }
    		
	public static void main(String[] arg) {

try{

PrintStream f = new PrintStream(new FileOutputStream("Automate.test"));

boolean ok;
RatExpr ratexpr = null;
Etat etmp, etmp1, etmp2, etmp3, etmp4, etmp5;
Integer c, c1, c2;
int e1, e2, e3, e4;
HashSet ei = new HashSet();
Automate a1, a2;

f.println("Tests de la classe Automate\n");

//Test1

f.print("Test 1 : Automate() - Constructeur par defaut ... ");
Automate a=new Automate();
	if (a.getEtats().size()==1) {
	etmp = (Etat) a.getEtats().get(new Integer(0));

	ok = a.getNumEtatLibre()==1
	&& a.getAlphabet().isEmpty()
	&& a.getEtatsInitiaux().contains(etmp)
	&& etmp.isInitial()
	&& !etmp.isTerminal()
	&& a.getEtatsTerminaux().isEmpty()
	&& a.getTransitions().isEmpty()
	&& a.isDeterministe()
	&& a.isMinimal();

	if (ok)
		f.println("OK");
	else
	f.println("KO");
	}
	else
	f.println("KO");


//Test2

		f.print("Test 2 : Automate(Etat) - Constructeur à 1 argument ... ");

		etmp = new Etat(4,false,true);
		a=new Automate(etmp);

		if (a.getEtats().size()==1) {
		ok= a.getNumEtatLibre()==5
	&& a.getAlphabet().isEmpty()
	&& a.getEtats().containsValue(etmp)
	&& a.getEtatsInitiaux().contains(etmp)
	&& etmp.isInitial()
	&& etmp.isTerminal()
	&& a.getEtatsTerminaux().contains(etmp)
	&& a.getTransitions().isEmpty()
	&& a.isDeterministe()
	&& a.isMinimal();

		if (ok)
			f.println("OK");
		else
		f.println("KO");
		}
		else
		f.println("KO");


//Test3

		f.print("Test 3 : Automate(RatExpr ratexpr) - <cas base> ratexpr==null ...    "
		);

		ratexpr = null;
		a=new Automate(ratexpr);

		if (a.getEtats().size()==1) {
		etmp = (Etat) a.getEtats().get(new Integer(0));
		ok= a.getNumEtatLibre()==1
	&& a.getAlphabet().isEmpty()
			&& a.getEtatsInitiaux().contains(etmp)
	&& etmp.isInitial()
	&& !etmp.isTerminal()
	&& a.getEtatsTerminaux().isEmpty()
	&& a.getTransitions().isEmpty()
	&& a.isDeterministe()
	&& a.isMinimal();

		if (ok)
			f.println("OK");
		else
		f.println("KO");
		}
		else
		f.println("KO");


//Test4
		f.print(
		"Test 4 : Automate(RatExpr ratexpr) - <cas base> ratexpr==epsilon ... "
		);

		c = null;
		ratexpr = new RatExprTerm(c);
		a=new Automate(ratexpr);

		if (a.getEtats().size()==1) {
		etmp = (Etat) a.getEtats().get(new Integer(0));
		ok= a.getNumEtatLibre()==1
	&& a.getAlphabet().isEmpty() 
			&& a.getEtatsInitiaux().contains(etmp)
	&& etmp.isInitial()
	&& etmp.isTerminal()
	&& a.getEtatsTerminaux().contains(etmp)
	&& a.getTransitions().isEmpty()
	&& a.isDeterministe()
	&& a.isMinimal();

		if (ok)
			f.println("OK");
		else
		f.println("KO");
		}
		else
		f.println("KO");


//Test5

		f.print(
		"Test 5 : Automate(RatExpr ratexpr) - <cas base> ratexpr==a ...       "
		);

		c = new Integer(0);
		ratexpr = new RatExprTerm(c);
		a = new Automate(ratexpr);

		if (a.getEtats().size()==2) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp2 = (Etat) a.getEtats().get(new Integer(1));

		boolean transition = 								a.getTransitions().containsKey(etmp1)
		&& ((Map) a.getTransitions().get(etmp1)).containsKey(c)
		&& ((Set)((Map) a.getTransitions().get(etmp1)).get(c)).contains(etmp2);



		ok= a.getNumEtatLibre()==2
	&& a.getAlphabet().contains(c)

			&& a.getEtatsInitiaux().contains(etmp1)
	&& etmp1.isInitial()
	&& !etmp1.isTerminal()

	&& a.getEtatsTerminaux().contains(etmp2)
	&& !etmp2.isInitial()
	&& etmp2.isTerminal()

	&& transition
	&& a.isDeterministe()
	&& a.isMinimal();

		if (ok)
			f.println("OK");
		else
		f.println("KO");
		}
		else
		f.println("KO");


//Test6a

		f.print(
		"Test 6a : Automate(RatExpr ratexpr) - <cas induction> ratexpr==a+, a==null ...    "
		);

		ratexpr = new RatExprPlus(null);
		a = new Automate(ratexpr);

		if (a.getEtats().size()==1) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));

		ok = a.getNumEtatLibre()==1

		&& a.getEtatsInitiaux().contains(etmp1)

		&& etmp1.isInitial()
		&& !etmp1.isTerminal()
		&& a.getTransitions().size()==0
		&& a.isDeterministe() == false
		&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");
//Test6b

		f.print(
		"Test 6b : Automate(RatExpr ratexpr) - <cas induction> ratexpr==a+, a==epsilon ... "
		);

		ratexpr = new RatExprPlus(new RatExprTerm(null));
		a = new Automate(ratexpr);

		if (a.getEtats().size()==1) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));

		boolean transition = 									a.getTransitions().containsKey(etmp1)
		&& ((Set)((Map) a.getTransitions().get(etmp1)).get(null)).contains(etmp1);


		ok = a.getNumEtatLibre()==1

		&& a.getEtatsInitiaux().contains(etmp1)

		&& etmp1.isInitial()
		&& etmp1.isTerminal()
		&& a.getTransitions().size()==1
		&& transition

		&& a.isDeterministe() == false
		&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");

//Test6c

		f.print(
		"Test 6c : Automate(RatExpr ratexpr) - <cas induction> ratexpr==a+ ...             "
		);

		c = new Integer(0);
		ratexpr = new RatExprPlus(new RatExprTerm(c));
		a = new Automate(ratexpr);

		if (a.getEtats().size()==2) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp2 = (Etat) a.getEtats().get(new Integer(1));

		boolean transition =
		a.getTransitions().containsKey(etmp1)
		&& a.getTransitions().containsKey(etmp2)
		&& ((Map) a.getTransitions().get(etmp1)).containsKey(c)
		&& ((Set)((Map) a.getTransitions().get(etmp1)).get(c)).contains(etmp2)
		&& ((Set)((Map) a.getTransitions().get(etmp2)).get(null)).contains(etmp1);



		ok= a.getNumEtatLibre()==2
		&& a.getAlphabet().contains(c)
		&& a.getEtatsInitiaux().contains(etmp1)

		&& etmp1.isInitial()
		&& !etmp1.isTerminal()

	&& a.getEtatsTerminaux().contains(etmp2)
	&& !etmp2.isInitial()
	&& etmp2.isTerminal()


	&& a.getTransitions().size()==2
	&& transition

	&& a.isDeterministe() == false
	&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO");
		}
		else
		f.println("KO");


//Test7a

		f.print(
		"Test 7a : Automate(RatExpr ratexpr) - <cas induction> ratexpr==a*, a==null ...    "
		);


		ratexpr = new RatExprEtoile(null);
		a=new Automate(ratexpr);

		if (a.getEtats().size()==1) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));


		ok= a.getNumEtatLibre()==1

	&& a.getEtatsInitiaux().contains(etmp1)
	&& etmp1.isInitial()
	&& etmp1.isTerminal()

	&& a.getEtatsTerminaux().size()==1
	&& a.getEtatsTerminaux().contains(etmp1)


	&& a.getTransitions().size()==0

	&& a.isDeterministe() == false
	&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");


//Test7b

		f.print(
		"Test 7b : Automate(RatExpr ratexpr) - <cas induction> ratexpr==a*, a==epsilon ... "
		);

		c = null;
		ratexpr = new RatExprEtoile(new RatExprTerm(c));
		a=new Automate(ratexpr);

		if (a.getEtats().size()==1) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));

		boolean transition = 									a.getTransitions().containsKey(etmp1)
		&& ((Set)((Map)a.getTransitions().get(etmp1)).get(null)).contains(etmp1);

		ok= a.getNumEtatLibre()==1
	&& etmp1.isInitial()
	&& etmp1.isTerminal()

	&& a.getEtatsTerminaux().size()==1
	&& a.getEtatsTerminaux().contains(etmp1)

	&& a.getTransitions().size()==1
	&& transition

	&& a.isDeterministe() == false
	&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");


//Test7c

		f.print(
		"Test 7c : Automate(RatExpr ratexpr) - <cas induction> ratexpr==a* ...             "
		);

		c = new Integer(0);
		ratexpr = new RatExprEtoile(new RatExprTerm(c));
		a=new Automate(ratexpr);

		if (a.getEtats().size()==2) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp2 = (Etat) a.getEtats().get(new Integer(1));


		boolean transition =
	a.getTransitions().containsKey(etmp1)
	&& a.getTransitions().containsKey(etmp2)
	&& ((Map) a.getTransitions().get(etmp1)).containsKey(c)
	&& ((Set)((Map) a.getTransitions().get(etmp1)).get(c)).contains(etmp2)
	&& ((Set)((Map) a.getTransitions().get(etmp2)).get(null)).contains(etmp1);



		ok= a.getNumEtatLibre()==2
	&& a.getAlphabet().contains(c)

			&& a.getEtatsInitiaux().contains(etmp1)
	&& etmp1.isInitial()
	&& etmp1.isTerminal()

	&& a.getEtatsTerminaux().size()==2
	&& a.getEtatsTerminaux().contains(etmp1)
	&& a.getEtatsTerminaux().contains(etmp2)
	&& !etmp2.isInitial()
	&& etmp2.isTerminal()


	&& a.getTransitions().size()==2
	&& transition

	&& a.isDeterministe() == false
	&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO");
		}
		else
		f.println("KO");


//Test8a
		f.print(
		"Test 8a : Automate(RatExpr ratexpr) - <cas induction> ratexpr==a|b, b==null ...    "
		);


		c1 = new Integer(1);

		ratexpr = new RatExprOu(new RatExprTerm(c1), null);
		a=new Automate(ratexpr);

		if (a.getEtats().size()==4) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp2 = (Etat) a.getEtats().get(new Integer(1));
		etmp3 = (Etat) a.getEtats().get(new Integer(2));
		etmp4 = (Etat) a.getEtats().get(new Integer(3));

		boolean transition =
	a.getTransitions().containsKey(etmp4)
	&& a.getTransitions().containsKey(etmp1)
	&& !a.getTransitions().containsKey(etmp3)
	&& ((Map) a.getTransitions().get(etmp1)).containsKey(c1)
	&& ((Set)((Map) a.getTransitions().get(etmp1)).get(c1)).contains(etmp2)
	&& ((Set)((Map) a.getTransitions().get(etmp4)).get(null)).contains(etmp1)
	&& ((Set)((Map) a.getTransitions().get(etmp4)).get(null)).contains(etmp3);



		ok= a.getNumEtatLibre()==4

	&& a.getAlphabet().size()==1
	&& a.getAlphabet().contains(c1)

	&& a.getEtatsInitiaux().contains(etmp4)
	&& etmp4.isInitial()
	&& !etmp4.isTerminal()

	&& !etmp1.isInitial()
	&& !etmp1.isTerminal()

	&& !etmp2.isInitial()
	&& etmp2.isTerminal()

	&& !etmp3.isInitial()
	&& !etmp3.isTerminal()

	&& a.getEtatsTerminaux().size()==1

	&& a.getEtatsTerminaux().contains(etmp2)
	&& !a.getEtatsTerminaux().contains(etmp3)

	&& a.getTransitions().size()==2

	&& transition
	&& a.isDeterministe() == false
	&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");


//Test8b
		f.print(
		"Test 8b : Automate(RatExpr ratexpr) - <cas induction> ratexpr==a|b, b==epsilon ... "
		);


		c1 = new Integer(1);

		ratexpr = new RatExprOu(new RatExprTerm(c1), new RatExprTerm(null));
		a=new Automate(ratexpr);

		if (a.getEtats().size()==4) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp2 = (Etat) a.getEtats().get(new Integer(1));
		etmp3 = (Etat) a.getEtats().get(new Integer(2));
		etmp4 = (Etat) a.getEtats().get(new Integer(3));

		boolean transition =
	a.getTransitions().containsKey(etmp4)
	&& a.getTransitions().containsKey(etmp1)
	&& !a.getTransitions().containsKey(etmp3)
	&& ((Map) a.getTransitions().get(etmp1)).containsKey(c1)
	&& ((Set)((Map) a.getTransitions().get(etmp1)).get(c1)).contains(etmp2)
	&& ((Set)((Map) a.getTransitions().get(etmp4)).get(null)).contains(etmp1)
	&& ((Set)((Map) a.getTransitions().get(etmp4)).get(null)).contains(etmp3);



		ok= a.getNumEtatLibre()==4

	&& a.getAlphabet().size()==1
	&& a.getAlphabet().contains(c1)

	&& a.getEtatsInitiaux().contains(etmp4)
	&& etmp4.isInitial()
	&& !etmp4.isTerminal()

	&& !etmp1.isInitial()
	&& !etmp1.isTerminal()

	&& !etmp2.isInitial()
	&& etmp2.isTerminal()

	&& !etmp3.isInitial()
	&& etmp3.isTerminal()

	&& a.getEtatsTerminaux().size()==2

	&& a.getEtatsTerminaux().contains(etmp2)
	&& a.getEtatsTerminaux().contains(etmp3)

	&& a.getTransitions().size()==2

	&& transition
	&& a.isDeterministe() == false
	&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");


//Test8c
		f.print(
		"Test 8c : Automate(RatExpr ratexpr) - <cas induction> ratexpr==a|b ...             "
		);


		c1 = new Integer(0);
		c2 = new Integer(1);

		ratexpr = new RatExprOu(new RatExprTerm(c1), new RatExprTerm(c2));
		a=new Automate(ratexpr);

		if (a.getEtats().size()==5) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp2 = (Etat) a.getEtats().get(new Integer(1));
		etmp3 = (Etat) a.getEtats().get(new Integer(2));
		etmp4 = (Etat) a.getEtats().get(new Integer(3));
		etmp5 = (Etat) a.getEtats().get(new Integer(4));

		boolean transition =
	a.getTransitions().containsKey(etmp5)
	&& a.getTransitions().containsKey(etmp1)
	&& a.getTransitions().containsKey(etmp3)
	&& ((Map) a.getTransitions().get(etmp1)).containsKey(c1)
	&& ((Map) a.getTransitions().get(etmp3)).containsKey(c2)
	&& ((Set)((Map) a.getTransitions().get(etmp1)).get(c1)).contains(etmp2)
	&& ((Set)((Map) a.getTransitions().get(etmp3)).get(c2)).contains(etmp4)
	&& ((Set)((Map) a.getTransitions().get(etmp5)).get(null)).contains(etmp1)
	&& ((Set)((Map) a.getTransitions().get(etmp5)).get(null)).contains(etmp3);



		ok= a.getNumEtatLibre()==5

	&& a.getAlphabet().size()==2
	&& a.getAlphabet().contains(c1)
	&& a.getAlphabet().contains(c2)

	&& a.getEtatsInitiaux().contains(etmp5)
	&& etmp5.isInitial()
	&& !etmp5.isTerminal()

	&& !etmp1.isInitial()
	&& !etmp1.isTerminal()

	&& !etmp2.isInitial()
	&& etmp2.isTerminal()

	&& !etmp3.isInitial()
	&& !etmp3.isTerminal()

	&& !etmp4.isInitial()
	&& etmp4.isTerminal()

	&& a.getEtatsTerminaux().size()==2

	&& a.getEtatsTerminaux().contains(etmp2)
	&& a.getEtatsTerminaux().contains(etmp4)

	&& a.getTransitions().size()==3

	&& transition
	&& a.isDeterministe() == false
	&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");


//Test9a

		f.print(
		"Test 9a : Automate(RatExpr ratexpr) - <cas induction> ratexpr==a.b, a==null ...    "
		);

		c1 = new Integer(0);
		ratexpr = new RatExprPoint(new RatExprTerm(c1), null);
		a=new Automate(ratexpr);

		if (a.getEtats().size()==3) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp2 = (Etat) a.getEtats().get(new Integer(1));
		etmp3 = (Etat) a.getEtats().get(new Integer(2));



		boolean transition =
	a.getTransitions().containsKey(etmp1)
	&& a.getTransitions().containsKey(etmp2)
	&& !a.getTransitions().containsKey(etmp3)
	&& ((Map) a.getTransitions().get(etmp1)).containsKey(c1)
	&& ((Set)((Map) a.getTransitions().get(etmp1)).get(c1)).contains(etmp2)
	&& ((Set)((Map) a.getTransitions().get(etmp2)).get(null)).contains(etmp3);


		ok= a.getNumEtatLibre()==3

		&& a.getAlphabet().size()==1
	&& a.getAlphabet().contains(c1)


	&& a.getEtatsInitiaux().contains(etmp1)

	&& etmp1.isInitial()
	&& !etmp1.isTerminal()

	&& !etmp2.isInitial()
	&& !etmp2.isTerminal()

	&& !etmp3.isInitial()
	&& !etmp3.isTerminal()

	&& a.getEtatsTerminaux().size()==0
	&& a.getEtatsTerminaux().isEmpty()

	&& a.getTransitions().size()==2
	&& transition


	&& a.isDeterministe() == false
	&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");


//Test9b

		f.print(
		"Test 9b : Automate(RatExpr ratexpr) - <cas induction> ratexpr==a.b, a==epsilon ... "
		);
c1 = new Integer(0);
		ratexpr = new RatExprPoint(new RatExprTerm(c1), new RatExprTerm(null));
		a=new Automate(ratexpr);

		if (a.getEtats().size()==3) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp2 = (Etat) a.getEtats().get(new Integer(1));
		etmp3 = (Etat) a.getEtats().get(new Integer(2));



		boolean transition =
	a.getTransitions().containsKey(etmp1)
	&& a.getTransitions().containsKey(etmp2)
	&& !a.getTransitions().containsKey(etmp3)
	&& ((Map) a.getTransitions().get(etmp1)).containsKey(c1)
	&& ((Set)((Map) a.getTransitions().get(etmp1)).get(c1)).contains(etmp2)
	&& ((Set)((Map) a.getTransitions().get(etmp2)).get(null)).contains(etmp3);


		ok= a.getNumEtatLibre()==3

		&& a.getAlphabet().size()==1
	&& a.getAlphabet().contains(c1)


	&& a.getEtatsInitiaux().contains(etmp1)

	&& etmp1.isInitial()
	&& !etmp1.isTerminal()

	&& !etmp2.isInitial()
	&& !etmp2.isTerminal()

	&& !etmp3.isInitial()
	&& etmp3.isTerminal()

	&& a.getEtatsTerminaux().size()==1
	&& a.getEtatsTerminaux().contains(etmp3)

	&& a.getTransitions().size()==2
	&& transition


	&& a.isDeterministe() == false
	&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");


//Test9c

		f.print(
		"Test 9c : Automate(RatExpr ratexpr) - <cas induction> ratexpr==a.b ...             "
		);

		c1 = new Integer(0);
		c2 = new Integer(1);
		ratexpr = new RatExprPoint(new RatExprTerm(c1), new RatExprTerm(c2));
		a=new Automate(ratexpr);

		if (a.getEtats().size()==4) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp2 = (Etat) a.getEtats().get(new Integer(1));
		etmp3 = (Etat) a.getEtats().get(new Integer(2));
		etmp4 = (Etat) a.getEtats().get(new Integer(3));



		boolean transition =
	a.getTransitions().containsKey(etmp1)
	&& a.getTransitions().containsKey(etmp2)
	&& a.getTransitions().containsKey(etmp3)
	&& ((Map) a.getTransitions().get(etmp1)).containsKey(c1)
	&& ((Set)((Map) a.getTransitions().get(etmp1)).get(c1)).contains(etmp2)
	&& ((Map) a.getTransitions().get(etmp3)).containsKey(c2)
	&& ((Set)((Map) a.getTransitions().get(etmp3)).get(c2)).contains(etmp4)
	&& ((Set)((Map) a.getTransitions().get(etmp2)).get(null)).contains(etmp3);


		ok= a.getNumEtatLibre()==4

		&& a.getAlphabet().size()==2
	&& a.getAlphabet().contains(c1)
	&& a.getAlphabet().contains(c2)

	&& a.getEtatsInitiaux().contains(etmp1)

	&& etmp1.isInitial()
	&& !etmp1.isTerminal()

	&& !etmp2.isInitial()
	&& !etmp2.isTerminal()

	&& !etmp3.isInitial()
	&& !etmp3.isTerminal()

	&& !etmp4.isInitial()
	&& etmp4.isTerminal()

	&& a.getEtatsTerminaux().size()==1
	&& a.getEtatsTerminaux().contains(etmp4)

	&& a.getTransitions().size()==3
	&& transition


	&& a.isDeterministe() == false
	&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO");
		}
		else
		f.println("KO");


//Test10a
		f.print(
		"Test 10a : Automate(RatExpr ratexpr) - <cas induction> ratexpr==a^p p=0 ... "
		);

		c = new Integer(0);

		ratexpr = new RatExprPuiss(new RatExprTerm(c), 0);

		a = new Automate(ratexpr);

		if (a.getEtats().size()==1) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));

		ok=

	a.getNumEtatLibre()==1

	&& a.getAlphabet().isEmpty()

	&& a.getEtatsInitiaux().contains(etmp1)

	&& etmp1.isInitial()
	&& etmp1.isTerminal()

	&& a.getEtatsTerminaux().size()==1
	&& a.getEtatsTerminaux().contains(etmp1)

	&& a.isDeterministe()
	&& a.isMinimal();

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");


//Test10b
		f.print(
		"Test 10b : Automate(RatExpr ratexpr) - <cas induction> ratexpr==a^p p=2 ... "
		);

		c = new Integer(0);

		ratexpr = new RatExprPuiss(new RatExprTerm(c), 2);

		a = new Automate(ratexpr);

		if (a.getEtats().size()==4) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp2 = (Etat) a.getEtats().get(new Integer(1));
		etmp3 = (Etat) a.getEtats().get(new Integer(2));
		etmp4 = (Etat) a.getEtats().get(new Integer(3));



		boolean transition =
	a.getTransitions().size()==3
	&& a.getTransitions().containsKey(etmp1)
	&& a.getTransitions().containsKey(etmp2)
	&& a.getTransitions().containsKey(etmp3)
	&& ((Map) a.getTransitions().get(etmp1)).containsKey(c)
	&& ((Set)((Map) a.getTransitions().get(etmp1)).get(c)).contains(etmp2)
	&& ((Set)((Map) a.getTransitions().get(etmp2)).get(null)).contains(etmp3)
	&& ((Map) a.getTransitions().get(etmp3)).containsKey(c)
	&& ((Set)((Map) a.getTransitions().get(etmp3)).get(c)).contains(etmp4);


		ok=
	a.getNumEtatLibre()==4

	&& a.getAlphabet().size()==1
	&& a.getAlphabet().contains(c)


	&& a.getEtatsInitiaux().contains(etmp1)

	&& etmp1.isInitial()
	&& !etmp1.isTerminal()

	&& !etmp2.isInitial()
	&& !etmp2.isTerminal()

	&& !etmp3.isInitial()
	&& !etmp3.isTerminal()

	&& !etmp4.isInitial()
	&& etmp4.isTerminal()

	&& a.getEtatsTerminaux().size()==1
	&& a.getEtatsTerminaux().contains(etmp4)

	&& transition


	&& a.isDeterministe() == false
	&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO");
		}
		else
		f.println("KO");


//Test10c
		f.print(
		"Test 10c : Automate(RatExpr ratexpr) - <cas induction> ratexpr==a^p, p=2, a==null ...    "
		);

		ratexpr = new RatExprPuiss(null, 2);

		a = new Automate(ratexpr);

		if (a.getEtats().size()==3) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp2 = (Etat) a.getEtats().get(new Integer(1));
		etmp3 = (Etat) a.getEtats().get(new Integer(2));


		boolean transition =
	a.getTransitions().size()==1
	&& a.getTransitions().containsKey(etmp3)
	&& ((Map) a.getTransitions().get(etmp3)).containsKey(null)
	&& ((Set)((Map) a.getTransitions().get(etmp3)).get(null)).contains(etmp1)
	&& ((Set)((Map) a.getTransitions().get(etmp3)).get(null)).contains(etmp2);


	ok=
	a.getNumEtatLibre()==3

	&& a.getAlphabet().size()==0


	&& !etmp1.isInitial()
	&& !etmp1.isTerminal()

	&& !etmp2.isInitial()
	&& !etmp2.isTerminal()

	&& etmp3.isInitial()
	&& !etmp3.isTerminal()

	&& a.getEtatsTerminaux().size()==0

	&& transition

	&& !a.isDeterministe()
	&& !a.isMinimal();

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");

//Test10d
		f.print(
		"Test 10d : Automate(RatExpr ratexpr) - <cas induction> ratexpr==a^p, p=2, a==epsilon ... "
		);

		ratexpr = new RatExprPuiss(new RatExprTerm(null), 2);

		a = new Automate(ratexpr);

		if (a.getEtats().size()==2) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp2 = (Etat) a.getEtats().get(new Integer(1));





		boolean transition =
	a.getTransitions().size()==1
	&& a.getTransitions().containsKey(etmp1)
	&& ((Set)((Map) a.getTransitions().get(etmp1)).get(null)).contains(etmp2);


	ok=
	a.getNumEtatLibre()==2

	&& a.getAlphabet().size()==0


	&& etmp1.isInitial()
	&& !etmp1.isTerminal()


	&& !etmp2.isInitial()
	&& etmp2.isTerminal()

	&& a.getEtatsTerminaux().size()==1

	&& transition


	&& a.isDeterministe() == false
	&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");


//Test *6a
		f.print(
		"Test *6a : determinise() - Automate du Test 6a ... "
		);

		ratexpr = new RatExprPlus(null);
		a1 = new Automate(ratexpr);

		a = a1.determinise();


		if (a.getEtats().size()==1) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));

		ok = a.getNumEtatLibre()==1

		&& a.getEtatsInitiaux().contains(etmp1)

		&& etmp1.isInitial()
		&& !etmp1.isTerminal()
		&& a.getTransitions().size()==0
		&& a.isDeterministe()
		&& !a.isMinimal();

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");


//Test *6b

		f.print(
		"Test *6b : determinise() - Automate du Test 6b ... "
		);

		ratexpr = new RatExprPlus(new RatExprTerm(null));
		a1 = new Automate(ratexpr);

		a = a1.determinise();

		if (a.getEtats().size()==1) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));




		ok = a.getNumEtatLibre()==1

		&& a.getEtatsInitiaux().contains(etmp1)

		&& etmp1.isInitial()
		&& etmp1.isTerminal()

		&& a.getTransitions().isEmpty()

		&& a.isDeterministe() == true
		&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");

//Test *6c

		f.print(
		"Test *6c : determinise() - Automate du Test 6c ... "
		);

		c = new Integer(0);
		ratexpr = new RatExprPlus(new RatExprTerm(c));
		a1 = new Automate(ratexpr);

		a = a1.determinise();

		if (a.getEtats().size()==2) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp2 = (Etat) a.getEtats().get(new Integer(1));

		boolean transition =
		a.getTransitions().size()==2
		&& a.getTransitions().containsKey(etmp1)
		&& a.getTransitions().containsKey(etmp2)
		&& ((Map) a.getTransitions().get(etmp1)).containsKey(c)
		&& ((Set)((Map) a.getTransitions().get(etmp1)).get(c)).contains(etmp2)
		&& ((Set)((Map) a.getTransitions().get(etmp2)).get(c)).contains(etmp2)
		;

		ok = a.getNumEtatLibre()==2
		&& a.getAlphabet().contains(c)
		&& a.getEtatsInitiaux().contains(etmp1)

		&& etmp1.isInitial()
		&& !etmp1.isTerminal()

		&& !etmp2.isInitial()
		&& etmp2.isTerminal()
		&& a.getEtatsTerminaux().contains(etmp2)

		&& transition

		&& a.isDeterministe() == true
		&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");

//Test *7a

		f.print(
		"Test *7a : determinise() - Automate du Test 7a ... "
		);


		ratexpr = new RatExprEtoile(null);
		a1 = new Automate(ratexpr);

		a = a1.determinise();

		if (a.getEtats().size()==1) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));


		ok= a.getNumEtatLibre()==1

	&& a.getEtatsInitiaux().contains(etmp1)
	&& etmp1.isInitial()
	&& etmp1.isTerminal()

	&& a.getEtatsTerminaux().size()==1
	&& a.getEtatsTerminaux().contains(etmp1)


	&& a.getTransitions().isEmpty()

	&& a.isDeterministe() == true
	&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");

//Test *7b

		f.print(
		"Test *7b : determinise() - Automate du Test 7b ... "
		);

		c = null;
		ratexpr = new RatExprEtoile(new RatExprTerm(c));
		a1 = new Automate(ratexpr);

		a = a1.determinise();
		if (a.getEtats().size()==1) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));

		ok= a.getNumEtatLibre()==1
	&& etmp1.isInitial()
	&& etmp1.isTerminal()

	&& a.getEtatsTerminaux().size()==1
	&& a.getEtatsTerminaux().contains(etmp1)

	&& a.getTransitions().isEmpty()

	&& a.isDeterministe() == true
	&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");

//Test *7c

		f.print(
		"Test *7c : determinise() - Automate du Test 7c ... "
		);

		c = new Integer(0);
		ratexpr = new RatExprEtoile(new RatExprTerm(c));
		a1=new Automate(ratexpr);

		a = a1.determinise();

		if (a.getEtats().size()==2) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp2 = (Etat) a.getEtats().get(new Integer(1));


		boolean transition =
	a.getTransitions().containsKey(etmp1)
	&& a.getTransitions().containsKey(etmp2)
	&& ((Map) a.getTransitions().get(etmp1)).containsKey(c)
	&& ((Set)((Map) a.getTransitions().get(etmp1)).get(c)).contains(etmp2)
	&& ((Set)((Map) a.getTransitions().get(etmp2)).get(c)).contains(etmp2);



		ok= a.getNumEtatLibre()==2
	&& a.getAlphabet().contains(c)

			&& a.getEtatsInitiaux().contains(etmp1)
	&& etmp1.isInitial()
	&& etmp1.isTerminal()
	&& a.getEtatsTerminaux().contains(etmp1)

	&& !etmp2.isInitial()
	&& etmp2.isTerminal()
	&& a.getEtatsTerminaux().contains(etmp2)

	&& a.getEtatsTerminaux().size()==2

	&& a.getTransitions().size()==2
	&& transition

	&& a.isDeterministe() == true
	&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");


//Test *8a
		f.print(
		"Test *8a : determinise() - Automate du Test 8a ... "
		);


		c1 = new Integer(1);

		ratexpr = new RatExprOu(new RatExprTerm(c1), null);
		a1 = new Automate(ratexpr);

		a = a1.determinise();

		if (a.getEtats().size()==2) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp2 = (Etat) a.getEtats().get(new Integer(1));

		boolean transition =
	a.getTransitions().size()==1
	&& a.getTransitions().containsKey(etmp1)
	&& ((Map) a.getTransitions().get(etmp1)).containsKey(c1)
	&& ((Set)((Map) a.getTransitions().get(etmp1)).get(c1)).contains(etmp2);


		ok= a.getNumEtatLibre()==2

	&& a.getAlphabet().size()==1
	&& a.getAlphabet().contains(c1)

	&& a.getEtatsInitiaux().contains(etmp1)
	&& etmp1.isInitial()
	&& !etmp1.isTerminal()

	&& !etmp2.isInitial()
	&& etmp2.isTerminal()
	&& a.getEtatsTerminaux().size()==1

	&& a.getEtatsTerminaux().contains(etmp2)

	&& transition

	&& a.isDeterministe() == true
	&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");


//Test *8b
		f.print(
		"Test *8b : determinise() - Automate du Test 8b ... "
		);

		c1 = new Integer(1);

		ratexpr = new RatExprOu(new RatExprTerm(c1), new RatExprTerm(null));
		a1 = new Automate(ratexpr);

		a = a1.determinise();

		if (a.getEtats().size()==2) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp2 = (Etat) a.getEtats().get(new Integer(1));

		boolean transition =
	a.getTransitions().size()==1
	&& a.getTransitions().containsKey(etmp1)
	&& ((Map) a.getTransitions().get(etmp1)).containsKey(c1)
	&& ((Set)((Map) a.getTransitions().get(etmp1)).get(c1)).contains(etmp2);


		ok= a.getNumEtatLibre()==2

	&& a.getAlphabet().size()==1
	&& a.getAlphabet().contains(c1)

	&& a.getEtatsInitiaux().contains(etmp1)
	&& etmp1.isInitial()
	&& etmp1.isTerminal()
	&& a.getEtatsTerminaux().contains(etmp1)

	&& !etmp2.isInitial()
	&& etmp2.isTerminal()
	&& a.getEtatsTerminaux().contains(etmp2)

	&& a.getEtatsTerminaux().size()==2

	&& transition

	&& a.isDeterministe() == true
	&& a.isMinimal() == false;


		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");


//Test *8c
		f.print(
		"Test *8c : determinise() - Automate du Test 8c ... "
		);


		c1 = new Integer(0);
		c2 = new Integer(1);

		ratexpr = new RatExprOu(new RatExprTerm(c1), new RatExprTerm(c2));
		a1 = new Automate(ratexpr);

		a = a1.determinise();


		if (a.getEtats().size()==3) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp2 = (Etat) a.getEtats().get(new Integer(1));
		etmp3 = (Etat) a.getEtats().get(new Integer(2));

		boolean transition =
	a.getTransitions().size()==1


	&& a.getTransitions().containsKey(etmp1)
	&& ((Map) a.getTransitions().get(etmp1)).containsKey(c1)
	&& ((Map) a.getTransitions().get(etmp1)).containsKey(c2)
	&& ((Set)((Map) a.getTransitions().get(etmp1)).get(c1)).contains(etmp3)
	&& ((Set)((Map) a.getTransitions().get(etmp1)).get(c2)).contains(etmp2);

	ok= a.getNumEtatLibre()==3

	&& a.getAlphabet().size()==2
	&& a.getAlphabet().contains(c1)
	&& a.getAlphabet().contains(c2)

	&& etmp1.isInitial()
	&& !etmp1.isTerminal()
	&& a.getEtatsInitiaux().contains(etmp1)

	&& !etmp2.isInitial()
	&& etmp2.isTerminal()

	&& !etmp3.isInitial()
	&& etmp3.isTerminal()

	&& a.getEtatsTerminaux().size()==2
	&& a.getEtatsTerminaux().contains(etmp2)
	&& a.getEtatsTerminaux().contains(etmp3)

	&& transition

	&& a.isDeterministe() == true
	&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");

//Test *9a

		f.print(
		"Test *9a : determinise() - Automate du Test 9a ... "
		);

		c1 = new Integer(0);
		ratexpr = new RatExprPoint(new RatExprTerm(c1), null);
		a1 = new Automate(ratexpr);

		a = a1.determinise();

		if (a.getEtats().size()==2) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp2 = (Etat) a.getEtats().get(new Integer(1));

		boolean transition =
	a.getTransitions().size()==1
	&& a.getTransitions().containsKey(etmp1)
	&& ((Map) a.getTransitions().get(etmp1)).containsKey(c1)
	&& ((Set)((Map) a.getTransitions().get(etmp1)).get(c1)).contains(etmp2);


		ok= a.getNumEtatLibre()==2

	&& a.getAlphabet().size()==1
	&& a.getAlphabet().contains(c1)

	&& a.getEtatsInitiaux().contains(etmp1)

	&& etmp1.isInitial()
	&& !etmp1.isTerminal()

	&& !etmp2.isInitial()
	&& !etmp2.isTerminal()

	&& a.getEtatsTerminaux().size()==0
	&& a.getEtatsTerminaux().isEmpty()

	&& transition

	&& a.isDeterministe() == true
	&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");


//Test*9b

		f.print(
		"Test *9b : determinise() - Automate du Test 9b ... "
		);

		c1 = new Integer(0);
		ratexpr = new RatExprPoint(new RatExprTerm(c1), new RatExprTerm(null));
		a1 = new Automate(ratexpr);

		a = a1.determinise();

		if (a.getEtats().size()==2) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp2 = (Etat) a.getEtats().get(new Integer(1));

		boolean transition =
	a.getTransitions().size()==1
	&& a.getTransitions().containsKey(etmp1)
	&& ((Map) a.getTransitions().get(etmp1)).containsKey(c1)
	&& ((Set)((Map) a.getTransitions().get(etmp1)).get(c1)).contains(etmp2);


		ok= a.getNumEtatLibre()==2

	&& a.getAlphabet().size()==1
	&& a.getAlphabet().contains(c1)

	&& a.getEtatsInitiaux().contains(etmp1)

	&& etmp1.isInitial()
	&& !etmp1.isTerminal()

	&& !etmp2.isInitial()
	&& etmp2.isTerminal()

	&& a.getEtatsTerminaux().size()==1
	&& a.getEtatsTerminaux().contains(etmp2)

	&& transition

	&& a.isDeterministe() == true
	&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");


//Test *9c

		f.print(
		"Test *9c : determinise() - Automate du Test 9c ... "
		);

		c1 = new Integer(0);
		c2 = new Integer(1);
		ratexpr = new RatExprPoint(new RatExprTerm(c1), new RatExprTerm(c2));
		a1 = new Automate(ratexpr);

		a = a1.determinise();

		if (a.getEtats().size()==3) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp2 = (Etat) a.getEtats().get(new Integer(1));
		etmp3 = (Etat) a.getEtats().get(new Integer(2));



		boolean transition =
	a.getTransitions().size()==2
	&& a.getTransitions().containsKey(etmp1)
	&& a.getTransitions().containsKey(etmp2)
	&& ((Map) a.getTransitions().get(etmp1)).containsKey(c1)
	&& ((Set)((Map) a.getTransitions().get(etmp1)).get(c1)).contains(etmp2)
	&& ((Map) a.getTransitions().get(etmp2)).containsKey(c2)
	&& ((Set)((Map) a.getTransitions().get(etmp2)).get(c2)).contains(etmp3);


		ok= a.getNumEtatLibre()==3

	&& a.getAlphabet().size()==2
	&& a.getAlphabet().contains(c1)
	&& a.getAlphabet().contains(c2)

	&& a.getEtatsInitiaux().contains(etmp1)

	&& etmp1.isInitial()
	&& !etmp1.isTerminal()

	&& !etmp2.isInitial()
	&& !etmp2.isTerminal()

	&& !etmp3.isInitial()
	&& etmp3.isTerminal()

	&& a.getEtatsTerminaux().size()==1

	&& transition

	&& a.isDeterministe() == true
	&& a.isMinimal() == false;

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");


//Test *10a

		f.print(
		"Test *10a : determinise() - Automate du Test 10a ... "
		);

		c = new Integer(0);

		ratexpr = new RatExprPuiss(new RatExprTerm(c), 0);

		a1 = new Automate(ratexpr);

		a = a1.determinise();

		if (a.getEtats().size()==1) {

		etmp1 = (Etat) a.getEtats().get(new Integer(0));

		ok=
	a.getNumEtatLibre()==1

	&& a.getAlphabet().isEmpty()

	&& a.getEtatsInitiaux().contains(etmp1)

	&& etmp1.isInitial()
	&& etmp1.isTerminal()

	&& a.getEtatsTerminaux().size()==1
	&& a.getEtatsTerminaux().contains(etmp1)


	&& a.isDeterministe()
	&& a.isMinimal();

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");


//Test *10b
		f.print(
		"Test *10b : determinise() - Automate du Test 10b ... "
		);

		c = new Integer(0);

		ratexpr = new RatExprPuiss(new RatExprTerm(c), 2);

		a1 = new Automate(ratexpr);

		a = a1.determinise();

		if (a.getEtats().size()==3) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp2 = (Etat) a.getEtats().get(new Integer(1));
		etmp3 = (Etat) a.getEtats().get(new Integer(2));



		boolean transition =
	a.getTransitions().size()==2
	&& a.getTransitions().containsKey(etmp1)
	&& a.getTransitions().containsKey(etmp2)
	&& ((Map) a.getTransitions().get(etmp1)).containsKey(c1)
	&& ((Set)((Map) a.getTransitions().get(etmp1)).get(c1)).contains(etmp2)
	&& ((Map) a.getTransitions().get(etmp2)).containsKey(c1)
	&& ((Set)((Map) a.getTransitions().get(etmp2)).get(c1)).contains(etmp3);


		ok= a.getNumEtatLibre()==3

	&& a.getAlphabet().size()==1
	&& a.getAlphabet().contains(c1)

	&& a.getEtatsInitiaux().contains(etmp1)

	&& etmp1.isInitial()
	&& !etmp1.isTerminal()

	&& !etmp2.isInitial()
	&& !etmp2.isTerminal()

	&& !etmp3.isInitial()
	&& etmp3.isTerminal()

	&& a.getEtatsTerminaux().size()==1

	&& transition

	&& a.isDeterministe() == true
	&& a.isMinimal() == false;


		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");


//Test *10c
		f.print(
		"Test *10c : determinise() - Automate du Test 10c ... "
		);

		ratexpr = new RatExprPuiss(null, 2);

		a1 = new Automate(ratexpr);

		a = a1.determinise();

		if (a.getEtats().size()==1) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));


		ok=
	a.getNumEtatLibre()==1

	&& a.getAlphabet().size()==0

	&& etmp1.isInitial()
	&& !etmp1.isTerminal()

	&& a.getEtatsTerminaux().isEmpty()

	&& a.isDeterministe()
	&& !a.isMinimal();

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");

//Test *10d
		f.print(
		"Test *10d : determinise() - Automate du Test 10d ... "
		);

		ratexpr = new RatExprPuiss(new RatExprTerm(null), 2);

		a1 = new Automate(ratexpr);

		a = a1.determinise();

		if (a.getEtats().size()==1) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));


		ok=
	a.getNumEtatLibre()==1

	&& a.getAlphabet().size()==0

	&& etmp1.isInitial()
	&& etmp1.isTerminal()

	&& a.getEtatsTerminaux().contains(etmp1)

	&& a.isDeterministe()
	&& !a.isMinimal();

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");

//Test **1
		f.print(
		"Test **1 : minimise() - 3 etats -> 2 etats "
		);

		c = new Integer(0);

		Etat et1 = new Etat(0, true, false);

		a1 = new Automate(et1);
		e1 = et1.getNum().intValue();
		e2 = a1.ajoutEtat(false, false);
		e3 = a1.ajoutEtat(false, true);

		a1.ajoutTransition(e1, c, e3);
		a1.ajoutTransition(e2, c, e3);

		a = a1.minimise();

		if (a.getEtats().size()==2) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp3 = (Etat) a.getEtats().get(new Integer(2));

		ok =
	a.getNumEtatLibre()==3

	&& a.getAlphabet().size()==1

	&& et1.isInitial()
	&& !et1.isTerminal()

	&& !etmp3.isInitial()
	&& etmp3.isTerminal()
	&& a.getEtatsTerminaux().contains(etmp3)

	&& a.isDeterministe()
	&& a.isMinimal();

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");


//Test **2
		f.print(
		"Test **2 : minimise() - 4 etats -> 3 etats "
		);

		c = new Integer(0);

		et1 = new Etat(0, true, false);

		a1 = new Automate(et1);
		e1 = et1.getNum().intValue();
		e2 = a1.ajoutEtat(false, false);
		e3 = a1.ajoutEtat(false, false);
		e4 = a1.ajoutEtat(false, true);

		a1.ajoutTransition(e1, c1, e3);
		a1.ajoutTransition(e2, c1, e3);
		a1.ajoutTransition(e1, c2, e4);
		a1.ajoutTransition(e2, c2, e4);

		a = a1.minimise();

		if (a.getEtats().size()==3) {
		etmp1 = (Etat) a.getEtats().get(new Integer(0));
		etmp3 = (Etat) a.getEtats().get(new Integer(2));
		etmp4 = (Etat) a.getEtats().get(new Integer(3));

		ok =
	a.getNumEtatLibre()==4

	&& a.getAlphabet().size()==2

	&& et1.isInitial()
	&& !et1.isTerminal()

	&& !etmp3.isInitial()
	&& !etmp3.isTerminal()

	&& !etmp4.isInitial()
	&& etmp4.isTerminal()
	&& a.getEtatsTerminaux().contains(etmp4)

	&& a.isDeterministe()
	&& a.isMinimal();

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");

//Test **8c
		f.print(
		"Test **8c : minimise() - Automate *8c ... "
		);


		c1 = new Integer(0);
		c2 = new Integer(1);

		ratexpr = new RatExprOu(new RatExprTerm(c1), new RatExprTerm(c2));
		a=new Automate(ratexpr);

		a = a.determinise();
		a = a.minimise();
		if (a.getEtats().size()==2) {
		etmp3 = (Etat) a.getEtats().get(new Integer(2));
		etmp1 = (Etat) a.getEtats().get(new Integer(0));

		boolean transition =
	a.getTransitions().size()==2
	&& a.getTransitions().containsKey(etmp1)
	&& ((Map) a.getTransitions().get(etmp1)).containsKey(c1)
	&& ((Map) a.getTransitions().get(etmp1)).containsKey(c2)
	&& ((Set)((Map) a.getTransitions().get(etmp1)).get(c1)).contains(etmp3)
	&& ((Set)((Map) a.getTransitions().get(etmp1)).get(c2)).contains(etmp3);



	ok= a.getNumEtatLibre()==3

	&& a.getAlphabet().size()==2
	&& a.getAlphabet().contains(c1)
	&& a.getAlphabet().contains(c2)

	&& a.getEtatsInitiaux().contains(etmp1)
	&& etmp1.isInitial()
	&& !etmp1.isTerminal()

	&& !etmp3.isInitial()
	&& etmp3.isTerminal()

	&& a.getEtatsTerminaux().size()==1

	&& a.getEtatsTerminaux().contains(etmp3)

	&& transition
	
	&& a.isDeterministe() == true
	&& a.isMinimal() == true;

		if (ok)
			f.println("OK");
		else
		f.println("KO1");
		}
		else
		f.println("KO2");



		}catch (FileNotFoundException e) {}


	}
	
} 

