% The Markov chain algorithm
%
:-unknown(_, fail).
/*
prob(Prob) :-
	accept([o, o, o, o, o, o, o, k, k, k, k, k, k, o, o, o, o, o, o, o], Prob).

% The start state
start(q1).

% The final states
final(q9).

transition(q1, o, q2, 0.5).
transition(q2, o, q2, 0.75).
transition(q2, k, q3, 0.25).
transition(q3, k, q3, 0.7).
transition(q3, o, q4, 0.3).
transition(q4, o, q4, 0.65).
transition(q1, o, q5, 0.5).
transition(q5, o, q5, 0.8).
transition(q5, k, q6, 0.2).
transition(q6, k, q6, 0.8).
transition(q6, o, q7, 0.2).
transition(q7, o, q7, 0.75).
transition(q7, k, q8, 0.25).
transition(q8, k, q8, 0.7).

silent(q4, q9, 0.35).
silent(q8, q9, 0.3).	
*/
accept(Observations, Probability) :-
	start(StartState),
	accept(Observations, StartState, 1.0, Probability).

accept([], State, Probability, Probability) :-
	final(State).
accept([Observation | Observations], State, Prob, ProbOut) :-
	transition(State, Observation, NextState, ProbTrans),
	NextProb is Prob * ProbTrans,
	accept(Observations, NextState, NextProb, ProbOut).
accept(Observations, State, ProbIn, ProbOut) :-
	silent(State, NextState, ProbTrans),
	NextProb is ProbIn * ProbTrans,
	accept(Observations, NextState, NextProb, ProbOut).


% A Non deterministic automaton

% The start state
start(q0).

% The final states
final(q5).

transition(q0, a, q1, 1.0).
transition(q1, b, q1, 0.2).
transition(q1, c, q2, 0.6).
transition(q1, c, q4, 0.2).
transition(q2, a, q3, 1.0).
transition(q4, a, q3, 1.0).
transition(q3, b, q5, 1.0).

prob(Prob) :-
	accept([a, b, b, b, c, a, b], Prob).

