How to find useless states in a finite state machine Prolog

Question

I have been thinking of a solution for finding all the useless states defined in a particular automaton and I know that one approach is to start moving from the start state and then ask for the following state all of these stored in the Prolog predicate database. I have had no luck in writing the code very well because I am learning Prolog. I wish someone could help me out with this. Here I leave what I have.

The finite state machine structure. fa_start -> the initial state, fa_move -> the valid move from one state to another, fa_final -> the final state.

% Start State
:- assert(fa_start(fa_1, s_0)).
% Final States 
:- assert(fa_final(fa_1, s_5)).

:- assert(fa_move(fa_1, s_0, s_1, a)).
:- assert(fa_move(fa_1, s_1, s_4, b)).
:- assert(fa_move(fa_1, s_0, s_2, c)).
:- assert(fa_move(fa_1, s_2, s_4, d)).
:- assert(fa_move(fa_1, s_2, s_5, e)).
:- assert(fa_move(fa_1, s_0, s_3, f)).
:- assert(fa_move(fa_1, s_3, s_5, g)).
:- assert(fa_move(fa_1, s_6, s_3, h)).
:- assert(fa_move(fa_1, s_6, s_7, i)).
:- assert(fa_move(fa_1, s_7, s_8, j)).

Now, here is the code I have been writing. The idea is to start with fa_start and then keep moving using valid fa_move until it cannot reach fa_final.

adjacent(fa, N, M):-
   fa_move(fa, N, M, _).

adjacent_recursive(fa, N, L):-
   fa_start(fa, N),
   findall(l,adjacent(fa,N,_),L).

find_paths(fa):-
   adjacent_recursive(fa,s_0,_).

Thank you in advance for all the help.

Answer 1

I know it's difficult to find accurate information related to my specific question. I have been working on it and finally found a solution, may it not be the best, but makes the deal. I owe the idea to this site. If you find bugs, it'd be welcome.

Now, the following code prints the useless states given a finite state automata implemented as above.

find_useless_states(FA):- retractall(utiles(_)),retractall(visited(_)),
        forall(fa_final(FA,S),assert(utiles(S))),
        find_useless_states2(FA).
find_useless_states2(FA):- retract(utiles(S)),
     not(visited(S)), assert(visited(S)),
     forall((fa_move(FA,Y,S,_), not(visited(Y))),(asserta(utiles(Y)))),
     find_useless_states2(FA).
find_useless_states2(_).

difference(L1, L2, R) :- intersection(L1, L2, I),
                     append(L1, L2, All),
                     subtract(All, I, R).

find_all_states_as_list(FA,L):- findall(X,fa_move(FA,X,_,_),M),findall(Y,fa_move(FA,_,Y,_),N),merge(M,N,LL),sort(LL,L).
find_useful_states_as_list(L):- findall(X,visited(X),L).

print_useless_states(FA):- find_all_states_as_list(FA,L),find_useful_states_as_list(M), difference(L,M,R), length(R,D),write(R),nl,write(D).

Hope it helps other people. Some code ideas have been used from questions posted here in stackoverflow. I thank the people who answered those.

Answer 2

It is possible to use the dynamic database for all such things, but it easily gets very difficult to maintain. I'd rather compile the file with your definitions, thus avoid to perform assertz/1 manually.

uselessstate(Aut, Usl) :-
   setof(S0, S^( closure0(adjacent(Aut), S0,S), fa_final(Aut,S) ), S0s),
   setof(t, A^B^( adjacent(Aut, A,B), (Usl=A;Usl=B) ), _),
   non_member(Usl, S0s).

unreachable(Aut, Usl) :-
   setof(S, S0^( fa_start(Aut, S0), closure0(adjacent(Aut), S0,S) ), Ss),
   setof(t, A^B^( adjacent(Aut, A,B), (Usl=A;Usl=B) ), _),
   non_member(Usl, Ss).

The definition of closure0/3 and non_member/2 is found in another answer.