유한 상태 기계에서 쓸모없는 상태를 찾는 방법 프롤로그

Question

나는 특정 오토 마톤에서 정의 된 모든 쓸모없는 상태를 찾아내는 해결책을 생각해 왔는데, 하나의 접근법은 시작 상태에서부터 시작하여 물어 보는 것이다. 다음 상태는 모두 Prolog 술어 데이터베이스에 저장됩니다. 나는 Prolog를 배우기 때문에 코드를 잘 작성하는 데 운이 없었습니다. 나는 누군가가 이것으로 나를 도울 수 있으면 좋겠다. 여기에 나는 가지고있는 것을 떠난다.

유한 상태 기계 구조. fa_start -> 초기 상태, fa_move -> 한 상태에서 다른 상태로의 유효한 이동, fa_final -> 최종 상태.

% 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)). 

이제 제가 작성한 코드는 다음과 같습니다. 아이디어는 fa_start으로 시작한 다음 fa_final에 도달 할 수 없을 때까지 유효한 fa_move를 사용하여 계속 이동하는 것입니다.

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,_). 

모든 도움을 주셔서 감사합니다.

Answer 1

내 특정 질문과 관련된 정확한 정보를 찾는 것이 어렵다는 것을 알고 있습니다. 나는 그것에 대해 연구 해왔고 결국 해결책을 찾았습니다. 최선은 아니지만 거래를합니다. 아이디어는 this site입니다. 벌레를 발견하면 환영 할거야.

이제 다음 코드는 위와 같이 구현 된 유한 상태 오토마타를 사용하여 쓸모없는 상태를 인쇄합니다.

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). 

다른 사람들에게 도움이되기를 바랍니다. 일부 코드 아이디어는 stackoverflow에 게시 된 질문에서 사용되었습니다. 나는 그 사람들에게 감사 드린다.

Answer 2

이러한 모든 작업에 동적 데이터베이스를 사용할 수는 있지만 관리하기가 쉽지 않습니다. 나는 당신의 정의로 파일을 컴파일하려고하므로 assertz/1을 수동으로 수행하는 것을 피하십시오. definition of closure0/3 및 non_member/2

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). 

는 다른 답변에서 발견된다.