Bottleneck in my recursive python code

Question

I wrote the below code using recursion to do CYK algorithm so that the Grammar G can generate any words having same number of a's followed by any number of b's but for some reason it is very slow, not sure why? When I use s2 it works, but if I used s1 which is a longer string it takes forever. Could anyone please advise as I can't figure out where is the bottleneck?

def fn(G, w, i, j, T):
    if T[i, j]:
        print '1'
        return T[i, j]
    elif i == j:
        for r in G:
            print '2'
            if r.endswith(w[i]) and r[0] not in T[i, j]:    
                print '3'
                T[i, j].append(r[0])
    else:
        print '4'
        for k in range(i, j):
            print '5'
            for a in fn(G, w, i, k, T):
                print '6'
                for b in fn(G, w, k+1, j, T):
                    print '7'
                    for r in G:
                        print '8'
                        if r.endswith(a+b) and r[0] not in T[i, j]:
                            print '9'
                            T[i, j].append(r[0])
    return T[i, j]


def fnmain(G, S, w):
    dict = {}
    for x in range(0, len(w)):
        for y in range(x, len(w)):
            dict[x,y] = []
    print dict        
    v = fn(G, w, 0, len(w) - 1, dict)
    print (w, v)
    if S in v:
        print ("T")
        return True
    else:
        print ("F")
        return False

G = ["S->AB", "S->XB", "T->AB", "T->XB", "X->AT", "A->a", "B->b"]

s1 = "aaaaabbbbb"
s1 = "aaaaaaaaabbbbbbbbb"

fnmain(G, "S", s1)

I've used cProfile as suggested by @wwii and below is the result:

When s1 = "aaaaabbbbb" when s1= "aaaaaaaaabbbbbbbbb"