Aiuto per metodo minimize

[Ankarir]

Ho un esame tra poco e non mi vuole proprio funzionare questo programma . E' un metodo di una classe DFA che minimizza l'automa generandone uno nuovo con il numero di stati minore possibile. La classe DFA è una classe che tratta di automi deterministici a stati finiti. Ho seguito l'algoritmo del prof ma funziona solo in caso di alcuni automi, non in altri, e non ne capisco il perché. Sotto al metodo vi scrivo i prototipi delle varie funzioni che ho usato.

public DFA minimize() {
        boolean[][] eq = new boolean[numberOfStates][numberOfStates];
        HashSet<Character> alfabeto = alphabet();
        boolean cambiamento = true;


        for(int i=0; i<numberOfStates; i++){
            for(int j=0; j<numberOfStates; j++){
                if((finalState(i) && finalState(j)) || (!finalState(i) && !finalState(j)))
                    eq[i][j] = true;
            }
        }


        while(cambiamento) {
            cambiamento=false;
            for(int i=0; i<numberOfStates; i++){
                for(int j=0; j<numberOfStates; j++){
                    if(eq[i][j]) {
                        for(char ch: alfabeto) {
                            int arrivoI = move(i,ch);
                            int arrivoJ = move(j,ch);
                            if(arrivoI!=-1 && arrivoJ!=-1 && !eq[arrivoI][arrivoJ]) {
                                eq[i][j]=false;
                                cambiamento=true;
                            }
                        }
                    }
                }
            }
        }
        int[] m = new int[numberOfStates];
        int min;
        for(int i=0; i<numberOfStates; i++){
            min=numberOfStates;
            for(int j=0; j<numberOfStates; j++){
                if(eq[i][j] && j<min)
                    min = j;
            }
            m[i]=min;
        }
        int k=0;


        for(int j=0; j<numberOfStates; j++){
            if(m[j]>k)
                k = m[j];
        }
        k++;
        DFA newDfa = new DFA(k);
        for(int i=0; i<numberOfStates; i++){
            int arrivo;
            for(char ch: alfabeto) {
                arrivo = move(i, ch);
                if(arrivo!=-1)
                    newDfa.setMove(m[i],ch,m[arrivo]);
            }
        }
        for(int fs: finalStates) {
            if(!newDfa.finalState(m[fs]))
                newDfa.addFinalState(m[fs]);
        }
        return newDfa;
    }

boolean finalState(int q)

restituisce se lo stato q è uno stato finale

int move(int q, char c)

restituisce lo stato di arrivo da q leggendo c

HashSet alfphabet()

restituisce l'alfabeto dell'automa

setMove(int p, char c, int q)

inserisce nell'automa una transazione da p a q tramite il carattere c

addFinalState(int q)

inserisce lo stato q tra gli stati finali

numberOfStates è una variabile privata della classe che, come da nome, indica il n° degli stati dell'automa


Vi ringrazio molto per qualsiasi aiuto

[Nikopol]

funziona solo in caso di alcuni automi, non in altri,

Probabilmente di ta problemi nel caso il DFA non sia completo.

Credo che il problema sia qui:

if(arrivoI!=-1 && arrivoJ!=-1 && !eq[arrivoI][arrivoJ]) {
      eq[i][j]=false;
      cambiamento=true;
}

Fai il controllo su eq[][] solo se entrambe le transizioni sono valide(se il dfa è completo non avrai mai problemi).
Nel caso il DFA non sia completo può capitare che per un dato carattere esista una transizione valida partendo dallo stato i ma non dallo stato j; in questo caso devi considerare i due stati distinguibili.

Potresti testare la validità degli stati di arrivo in xor:

if(arrivoI!=-1 && arrivoJ!=-1 && !eq[arrivoI][arrivoJ]) {
    eq[i][j]=false;
    cambiamento=true;
}
else if((arrivoI!=-1 ^ arrivoJ!=-1) && !eq[arrivoI][arrivoJ] ){
    eq[i][j]=false;
    cambiamento=true;
}

Potresti anche usare un unico if.

[Nikopol]

Anzi non hai neache bisogno di controllare che eq[arrivoI][arrivoJ] sia falso

else if((arrivoI!=-1 ^ arrivoJ!=-1)){
    eq[i][j]=false;
    cambiamento=true;
}

[Ankarir]

Ok, ora funziona molto meglio, grazie mille! Peccato solo che non rimuova stati pozzo o stati inutili. Penso sia un problema dell'algoritmo.

[Nikopol]

Figurati
Se per stato pozzo intendi lo stato di errore che raccoglie tutte le transizioni non valide allora credo sia normale che non venga rimosso durante minimizzazione.

[Ankarir]

Con stati pozzo, al plurale, intendo quegli stati del dfa che portano ad uno stato di errore. Esempio, il dfa A ha tre stati: q,f,s. Con f stato finale. Senza essere formale, con 0 da q vado in f. Sempre con 0 da f vado in s. s è uno stato pozzo, è inutile quindi tenerlo. Ecco questi stati, inclusi quelli inutili, secondo me andrebbero eliminati in minimize. Comunque dato che non appariva nell'algoritmo che ci ha consegnato il prof evito di implementarlo. Grazie ancora!