% Prolog Implementation of MIL for learning Regular grammars
% Figure 5: Metagol_R
% To run, please download yap6.0


:-use_module(library(lists)). 

/****************** Fig.5 MetagolR *********************/

parse(S,G1,G2,S1,S2,K1,K2) :- parse(s(0),S,[],G1,G2,S1,S2,K1,K2).
parse(Q,X,X,G1,G2,S,S,K1,K2) :- abduce(acceptor(Q),G1,G2,K1,K2).
parse(Q,[C|X],Y,G1,G2,S1,S2,K1,K2) :- 
	skolem(P,S1,S3),
	abduce(delta1(Q,C,P),G1,G3,K1,K3), 
	parse(P,X,Y,G3,G2,S3,S2,K3,K2).

abduce(X,G,G,K,K) :- member(X,G).
abduce(X,G,[X|G],s(K),K) :- not(member(X,G)).

skolem(s(N),[s(Pre)|SkolemConsts],[s(N),s(Pre)|SkolemConsts]):- N is Pre+1.
skolem(S,SkolemConsts,SkolemConsts):-member(S,SkolemConsts). 


/********************************* Queries ****************************************/
query(G):-
member(K0,[s(0),s(s(0)),s(s(s(0))),s(s(s(s(0)))),s(s(s(s(s(0)))))]), % iterative deepening bound
parse([],[],G1,[s(0)],S1,K0,K1), parse([0],G1,G2,S1,S2,K1,K2), parse([0,0],G2,G3,S2,S3,K2,K3), parse([1,1],G3,G4,S3,S4,K3,K4),
parse([0,0,0],G4,G5,S4,S5,K4,K5), parse([0,1,1],G5,G6,S5,S6,K5,K6), parse([1,0,1],G6,G,S6,S,K6,K),
not(parse([1],G,G,S,S,K,K)), not(parse([0,1],G,G,S,S,K,K)).

query_oneEx(G):-
parse([],[],G1,[s(0)],S1,K0,K1),parse([1,0,1],[],G,[s(0)],S,K_any,K).