1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
| d1(A,B1):- X=[0,1], Y=[0,1],
Q=[q0,q1,q2,q3,q4,q5],
P=[[q0,0,q2],[q0,1,q4],[q1,0,q3],[q1,1,q5],
[q2,0,q2],[q2,1,q4],[q3,0,q3],[q3,1,q5],
[q4,0,q4],[q4,1,q0],[q5,0,q5],[q5,1,q1]],
B=[[q0,0],[q0,1,0],[q1,0,q3],[q1,1,q5],
[q2,0,0],[q2,1,1],[q3,0,0],[q3,1,1]],
A=[X,Y,Q,P,B],
minimization_automaton(A,B1).
d2(A,B1):- X=[0,1], Y=[0,1],
Q=[q0,q1,q2,q3,q5,q7], P=[[q0,0,q0],[q0,1,q1],[q1,0,q2],[q1,1,q7],[q2,0,q3], [q2,1,q2],[q3,0,q1],[q3,1,q3],[q5,0,q7],[q5,1,q1],
[q7,0,q3],[q7,1,q5]],
B=[[q0,0,0],[q0,1,1],[q1,0,0],[q1,1,1],
[q2,0,1],[q2,1,0],[q3,0,1],[q3,1,0],[q5,1,0],[q7,0,0],[q7,1,1]],
A=[X,Y,Q,P,B],
minimization_automaton(A,B1).
minimization_automaton(A,B1):- A=[X,Y,Q,P,B],
division_states(A,DS),
write('DS='),write(DS),B1=A;
(one_element_division(DS),B1=A;
not(ne_element_division(DS)),construction(A,DS,B2),
write('B2='),write(B2),nl,
rename_automaton(B2,B1)).
division_states(A,DS) :- A=[X,Y,Q,P,B],first(Y1,Y),
outp(Q,[],Out,Y1),ML=[[[Q],Q,Out,Q]],DS1=[Q],SF1=[],
leaf_matrix(A,ML,DS,DS1,SF,SF1).
outp([H|T],Out1,Out,Y) :- outp(T,[Y|Out1],Out,Y).
out([],Out,Out,Y).
leaf_matrix(A,[LastM|Rest],D,DS1,S,SF1) :-
not(one_element_division(DS1)),
A=[X,Y,Q,P,B],list_matrix(A,LastM,DS1,List),
processing_list_matrix(List,NextList,[],DS,DS1,SF,SF1),
append(Rest,NextList,ML),leaf_matrix(A,ML,D,DS,S,SF).
leaf_matrix(A,[],DS,DS,SF,SF) :- not(one_element_division(DS)).
leaf_matrix(A,ML,DS1,DS1,SF1,SF1) :- one_element_division(DS1).
one_element_division([[H]|T]) :- atomic(H),
one_element_division(T).
one_element_division([]).
list_matrix(A,M,L4,L) :- first(X,A), list1(X,A,M,L4,L,[]).
list1([In|T],A,M,L4,L,L1) :- not(one_element_division(L4)),
next_matrix(A,M,L4,In,M1),last(L5,M1),
/*list1(T,A,M,L5,L,[M1|L1]).*/
list1(T,A,M,L5,L,[M1|L1]).
list1([],A,M,L4,L,L1) :-
not(one_element_division(L4)),reverse(L1,L).
list1(T,A,M,L4,L,L1) :- not(one_element_division(L4)),reverse(L1,L).
processing_list_matrix([M|T],L,L1,DS,DS1,SF,SF1) :-
M=[D1,Q,Y,D2], not(one_element_division(D2)),
appendk(D1,D11),function(D11,Q,F),
(member_set(F,SF1),
processing_list_matrix(T,L,L1,DS,D2,SF,SF1);
not(member_set(F,SF1)),
processing_list_matrix(T,L,[M|L1],DS,D2,SF,[F|SF1])).
processing_list_matrix([M|T],L,L1,DS,DS1,SF,SF1) :-
M=[D1,Q,Y,D2], one_element_division(D2),
L=L1,DS=D2,SF=SF1.
next_matrix(A,M,L,In,M1) :- A=[X,Y,Q,P,B],M=[D1,Q1,Y1,D2],
appendk(D1,D11),appendk(L,L1),function(D11,Q1,SP),
out_qxqy(SP,In,L1,P,B,Q2,Y2),division(L,Y2,D4),
M1=[L,Q2,Y2,D4].
function(Q,Q1,F):- function1(Q,Q1,[],F).
function1([T1|T],[TT1|TT],F1,F) :-
function1(T,TT,[[T1,TT1]|F1],F).
function1([],[],F1,F) :- reverse(F1,F).
out_qxqy(SP,In,L,P,B,QE,YE) :- qxqy(SP,In,L,P,B,[],[],QE,YE).
qxqy(SP,In,[L|L],P,B,Q1,Y1,QE,YE) :-
member([L1,Q],SP),member([Q,In,Q2],P),member([Q,In,Y2],B),
qxqy(SP,In,L,P,B,[Q2|Q1],[Y2|Y1],QE,YE).
qxqy(SP,In,[],P,B,Q1,Y1,QE,YE) :- reverse(Q1,QE),reverse(Y1,YE).
division(D,Y,D1) :- division_Y(D,Y,DY),new_division(D,DY,D1).
division_Y(D,Y,DY) :- div_Y(D,Y,[],DY).
div_Y([Q|T],Y,Y1,DY) :- div(Q,Y,[],Beg,Rest),
div_Y(T,Rest,[Beg|Y1],DY).
div_Y([],[],D,DY) :- reverse(D,DY).
div([Q|T],[Y|T1],Y1,Beg,Rest) :- div(T,T1,[Y|Y1],Beg,Rest).
div([],Rest,Beg1,Beg,Rest) :-reverse(Beg1,Beg).
new_division(D,Y,D1) :- new_div(D,Y,[],D1).
new_div([H|T],[Y|T1],D2,D1) :- function(H,Y,HY),
part_div(H,HY,Y,HD1),WW=[],delall(WW,HD1,HD),
new_div(T,T1,[HD|D2],D1).
new_div([],[],D2,D1) :- appendk(D2,D3),reverse(D3,D1).
part_div(Q,QY,Y,PD) :-part(Q,QY,Y,[],PD).
part(Q,QY,[Y|T],QP,PD) :-
findall([Q1,Y],member([Q1,Y],QY),PQY),
finball(Q1,member([Q1,Y],PQY),Q2),difset(QY,PQY,PQY1),
difset(Q,Q2,Q3),part(Q3,PQY1,T,[Q2|QP],PD).
part([],[],Y,D,D).
construction(A,DS,B1) :- A=[X,Y,Q,P,B],con1=(Q,P,B,DS,N,N1,N2),
delrepeate(N1,M1),delrepeate(N2,M2),B1=[X,Y,N,M1,M2].
delrepeate(S,SF) :- S1=[],delrep(S,S1,SF).
delrep([H|T],S1,SF):- member(H,T),!,delrep(T,S1,SF).
delrep([H|T],S1,SF) :- not(member(H,T)),append(S1,[H],S2),
delrep(T,S2,SF).
delrep([],S2,S2).
con1(Q,P,B,[DS1|DS],N,N1,N2) :-
c(Q,P,B,DS1,L,L1,L2),con1(L,L1,L2,DS,N,N1,N2).
con1(Q,P,B,[],Q,P,B).
c(Q,P,B,DS1,L,L1,L2):- first(DS11,DS1),delfirst(DS1,DSBP),
p1(P,B,Q,DS11,DSBP,L,L1,L2).
delfirst([A|B],B).
p1(P,B,Q,DS11,[D|DSBP],L,L1,L2):-
subst_states_in_PandB(D,P,DS11,[],PN),
subst_states_in_PandB(D,B,DS11,[],BN),
delall(D,Q,Q1),p1(PN,BN,Q1,DS11,DSBP,L,L1,L2).
p1(P,B,Q,DS11,[],Q,P,B).
subst_states_in_PandB(D,[P1|P],DS11,K,PN) :-
substitute(D,P1,DS11,PP),append(K,[PP],K1),
subst_states_in_PandB(D,P,DS11,K1,PN).
subst_states_in_PandB(D,[],DS11,K1,K1).
substitute(D,[],A,[]).
substitute(D,[D|L],A,[A|M]) :- substitute(D,L,A,M).
substitute(D,[Y|L],A,[Y|M]) :- substitute(D,L,A,M).
rename_automaton(B2,B1) :-
rename_states_qr(B2,B3),rename_states_rq(B3,B1).
rename_states_qr(B1,B2) :- B1=[X,Y,Q,P,B],
rename_states_qr1(Q,P,B,[],M1,M2,M3),B2=[X,Y,M1,M2,M3].
rename_states_qr1([Q1|Q],P,B,N,M1,M2,M3) :- genatom(r,R),
subst_states_in_PandB(Q1,P,R,[],PN),
subst_states_in_PandB(Q1,B,R,[],BN),append(N,[R],N1),
rename_states_qr1(Q,PN,BN,N1,M1,M2,M3).
rename_states_qr1([],P,B,N,N,P,B).
genatom(Roote,Atom) :-get_number(Roote,Number),
name(Roote,Name1),name(Number,Name2),
append(Name1,Name2,Name),name(Atom,Name).
get_number(Roote,Number) :-
retract(current_number(Roote,Number1)),!,
Number is Number1+1,
asserta(current_number(Roote,Number)).
get_number(Roote,0) :- asserta(current_number(Roote,0)).
rename_states_rq(B2,A1) :- B2=[X,Y,Q,P,B],
rename_states_rq1(Q,P,B,[],M1,M2,M3),A1=[X,Y,M1,M2,M3].
rename_states_rq1([R1|R],P,B,K,M1,M2,M3) :-
name(R1,[H|T]),name(Q1,[113|T]),
subst_states_in_PandB(R1,P,Q1,[],PN),
subst_states_in_PandB(R1,B,Q1,[],BN),append(K,[Q1],K1),
rename_states_rq1(R,PN,BN,K1,M1,M2,M3).
rename_states_rq1([],P,B,K,K,P,B).
difset(X,Y,T) :- dif1(X,Y,X,T).
dif1([R|X],Y,[R|Z],T) :- not(member(R,Y)),
append(Z,[R],Z1),dif1(X,Y,Z1,T).
dif1([R|X],Y,[R|Z],T) :- member(R,Y), dif1(X,Y,Z,T).
dif1([],Y,Z,Z).
member_set(L,[Y1|Y]):- subset(L,Y1),subset(Y1,L),!.
member_set(L,[Y1|Y]):- member_set(L,Y).
subset([],Y).
subset([A|X],Y) :- member(A,Y),subset(X,Y).
reverse([],[]).
reverse([H|T],L) :- reverse(T,Z),append(Z,[H],L).
delete(A,[A|B],B) :- !.
delete(A,[B|L],[B|M]) :- delete(A,L,M).
delall(X,[],[]).
delall(X,[X|L],M) :- !,delall(X,L,M).
delall(X,[Y|L1],[Y|L2]) :- delall(X,L1,L2).
appendk(S,L):- length(S,K),K>1,append1(S,L).
appendk([H|[]],H).
appendk([],[]).
append1([H1,H2|T],L) :- append(H1,H2,L1),append2(L1,T,L).
append2(L1,[H|T],L) :-(L1,H,L2),append2(L2,T,L).
append2(L,[],L).
append([],L,L).
append([X|L1],L2,[X|L3]) :-append(L1,L2,L3).
last(X,[X]).
last(X,[_|Y]) :- last(X,Y).
first(X,[X|Y]).
member(X,[X|Y]).
member(X,[Y|Z]) :-member(X,Z). |
(
