% The Hidden Markov model

% The start state
start(q1).

% The final states
final(q8).

transition(q1, o1, q2, 0.5, 0.6).
transition(q1, o2, q2, 0.5, 0.3).
transition(q1, k, q2, 0.5, 0.1).
transition(q2, o1, q2, 0.75, 0.6).
transition(q2, o2, q2, 0.75, 0.3).
transition(q2, k, q2, 0.75, 0.1).
transition(q2, o1, q3, 0.25, 0.0).
transition(q2, o2, q3, 0.25, 0.0).
transition(q2, k, q3, 0.25, 1.0).
transition(q3, o1, q3, 0.7, 0.0).
transition(q3, o2, q3, 0.7, 0.0).
transition(q3, k, q3, 0.7, 1.0).
transition(q3, o1, q4, 0.3, 0.65).
transition(q3, o2, q4, 0.3, 0.25).
transition(q3, k, q4, 0.3, 0.1).
transition(q4, o1, q4, 0.65, 0.65).
transition(q4, o2, q4, 0.65, 0.25).
transition(q4, k, q4, 0.65, 0.1).
transition(q1, o1, q5, 0.5, 0.3).
transition(q1, o2, q5, 0.5, 0.7).
transition(q1, k, q5, 0.5, 0.0).
transition(q5, o1, q5, 0.8, 0.3).
transition(q5, o2, q5, 0.8, 0.7).
transition(q5, k, q5, 0.8, 0.0).
transition(q5, o1, q6, 0.2, 0.0).
transition(q5, o2, q6, 0.2, 0.0).
transition(q5, k, q6, 0.2, 1.0).
transition(q6, o1, q6, 0.8, 0.0).
transition(q6, o2, q6, 0.8, 0.0).
transition(q6, k, q6, 0.8, 1.0).
transition(q6, o1, q7, 0.2, 0.65).
transition(q6, o2, q7, 0.2, 0.25).
transition(q6, k, q7, 0.2, 0.1).
transition(q7, o1, q7, 0.7, 0.65).
transition(q7, o2, q7, 0.7, 0.25).
transition(q7, k, q7, 0.7, 0.1).

silent(q4, q8, 0.35).
silent(q7, q8, 0.3).	

accept(Observations, States, Prob) :-
	start(StartState),
	accept(Observations, StartState, 1.0, States, Prob).

accept([], State, Probability, [State], Probability) :-
	final(State).
accept([Observ | Observs], State, Prob, [State | States], ProbOut) :-
	transition(State, Observ, NextState, ProbTrans, ProbObserve),
	ProbObserve =\= 0.0,
	NextProb is Prob * ProbTrans * ProbObserve,
	accept(Observs, NextState, NextProb, States, ProbOut).
accept(Observs, State, ProbIn, [State | States], ProbOut) :-
	silent(State, NextState, ProbTrans),
	NextProb is ProbIn * ProbTrans,
	accept(Observs, NextState, NextProb, States, ProbOut).

most_probable_path(Observ, MP_Path, MP_Prob) :-
	findall(-(Prob, States), accept(Observ, States, Prob), L),
	keysort(L, Sorted),
	append(_, [-(MP_Prob, MP_Path)], Sorted).


path(States, Prob) :-
	accept([o1, o2, o1, k, k, o1, o1], States, Prob).

mp(Path, Prob) :-
	most_probable_path([o1, o2, o1, k, k, o1, o1], Path, Prob).