DFA simulate

dfa.py

DFA={"A":{0:"B",1:"C"},"B":{0:None,1:"D"},"C":{0:"D",1:None},"D":{0:"A",1:"B"}}
def genstr(n,s,inputs):
    if n==0:
        inputs.append(s)
        return
    genstr(n-1,s+"0",inputs)
    genstr(n-1,s+"1",inputs)

def simulate():
    for n in range(1,15):
        count=0
        inputs=[]
        genstr(n,"",inputs)
        for inp in inputs:
            s="A"
            for c in inp:
                s=DFA[s][int(c)]
                if s==None:
                    break
            if s=="D":
                count+=1
        print n,count

simulate()