words = ['<s>', 'the', 'aged', 'bottle', 'flies', 'fast', '</s>']
k = len(words)


T = ['<s>', 'adj', 'adv', 'det', 'n', 'v', '</s>']
cardT = len(T)
a = [[0.0, 0.4, 0.2, 0.2, 0.1, 0.1, 0.0],
     [0.0, 0.2, 0.1, 0.0, 0.3, 0.2, 0.2],
     [0.0, 0.2, 0.2, 0.1, 0.1, 0.2, 0.2],
     [0.0, 0.3, 0.1, 0.0, 0.5, 0.1, 0.0],
     [0.0, 0.1, 0.1, 0.1, 0.2, 0.3, 0.2],
     [0.0, 0.2, 0.3, 0.1, 0.2, 0.0, 0.2], 
     [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]]


b = [[1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0], 
     [0.0, 0.0, 0.0, 0.5, 0.0, 0.0, 0.0],
     [0.0, 0.1, 0.0, 0.0, 0.0, 0.01, 0.0],
     [0.0, 0.0, 0.0, 0.0, 0.1, 0.1, 0.0],
     [0.0, 0.0, 0.0, 0.0, 0.1, 0.2, 0.0],
     [0.0, 0.1, 0.3, 0.0, 0.01, 0.1,0.0],
     [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0]]  

b = dict(zip(words,b))      




alpha = [None for _ in range(k)]
alpha[0] = b["<s>"]
for t in range(1,k-1):
    alpha[t] = [sum([alpha[t-1][i] *  a[i][j] for i in range(cardT)])*b[words[t]][j] for j in range(cardT)]


beta = [None for _ in range(k-1)]
beta[0] = [x[-1] for x in a]
words.reverse()
for t in range(1,k-1):
    beta[t] = [sum([ beta[t-1][j]*a[i][j]*b[words[t]][j] for j in range(cardT)]) for i in range(cardT)]
beta.reverse()
words.reverse()

alphabeta = [[x*y for (x,y) in zip(xs,ys)] for (xs,ys) in zip(alpha,beta)]
gamma =  [[entry/sum(entries) for entry in entries] for entries in alphabeta]
for group in gamma:
    print group