# Given
# Set of states: Array S
# Start state: s0
# End state: se
# Symbol sequence: Array w
# State transition probabilities: Matrix a
# Symbol emission probabilities: Matrix b
# alpha: Matrix alpha

# All indizes in arrays start on 1 in this pseudocode
 
# Returns
# Total probability: p

# Initialisation F1
foreach s in S do
   alpha [1][s] := a[s0][s]*b[s][w[1]]
done

# Induction F2
for i := 1 to length(w)-1 do
  foreach s in S do
    foreach s' in S do
      alpha[i+1][s] += alpha[i][s']*a[s'][s]
  	done
    alpha[i+1][s] *= b[s][w[i+1]]
  done
done

# Termination F3
foreach s in S do
  p += alpha[length(w)][s]*a[s][se]
done

return p