[Python] Čitanje iz rječnika, rekurzija, automati

Pozdrav!

Nadam se da ima tu Pythonovaca :D.

Evo, trebam malu pomoć, zapel sam i dalje ne ide. Stvar je ovakva, trebam napraviti simulator nedeterminističkog konačnog automata s epsilon prijelazima. Da sad tu to puno ne objašnjavam, evo kak sam ja to zamislio. Definiciju automata učitavam iz datoteke. Sve je to okej, muče me samo funkcije prijelaza, evo primjer ($ označava epsilon prijelaz):

F-je prijelaza se definiraju ovak: trenutno_stanje,ulazni_znak->sljedece_stanje

s0,$->s1,s2
s0,a->s1
s1,c->s3
s2,a->s3
s3,c->s3
s3,$->s4
s4,$->s5
s4,c->s2

Epsilon prijelaz znači da automat može skočiti u neko stanje čak i ako je niz (koji prima) prazan. Tj. iz ovog primjera vidimo da ako je početno stanje s0, automat će se nalaziti i u stanjima do kojih se može doći $-prijelazima, tj. i u s1 i u s2. Ako se nalazi u s3, $-prijelazima otići će i u s4 i u s5, tj. bit će u isto vrijeme i u s3 i u s4 i u s5.

E sad, ja sam te f-je prijelaza učital u dictionary. Key mi je tuple u kojem se nalazi trenutno_stanje i ulazni_znak, a value je sljedece_stanje, nalazi se u listi. Recimo za prvi redak dictionary mi izgleda ovak:

{('s0', '$'): ['s1', 's2']}

E sad, meni treba f-ja koja će provjeriti dali za neko trenutno stanje postoji $-prijelaz i ako da, naći koja su to sljedeća stanja i spremiti to sve u neku novu listu. Npr. za ('s0', '$'): ['s1', 's2'] spremiti u listu stanja s0, s1 i s2. Tada bi rekurzijom trebal provjeriti dali postoje još $-prijelazi za s1 i s2, pa ako da, za ta novo otkrivena stanja itd. E mene muči, kak to izvesti s ovim dictionaryem...

Evo pokušaja:

def epsilon_fun(initial_state_fun, state_dict):
    new_states = initial_state_fun
    if (initial_state_fun, '$') in state_dict.keys():

No, to ne radi, taj if uopće ne prolazi... Recimo da je initial_state_fun jednak s0. Po nekoj mojoj logici taj if bi provjerio dali postoji key ('s0', '$') u tom dictionaryu. Također ni if state_dict.has_key((initial_state_fun, '$')): ne šljaka. -.- Jel netko zna kak da riješim tu rekurzivnu f-ju?

EDIT: Riješeno sa join metodom.

def epsilon_fun(initial_state_fun, state_dict):
    new_states = initial_state_fun
    if state_dict.has_key((''.join(initial_state_fun), '$')):

Sad dalje, rekurzija -.-

Evo napisal sam novu f-ju za pretraživanje tih nizova:

def epsilon_fun(initial_state_fun, state_dict):
    new_states = initial_state_fun
    for state_index in new_states:
       if state_dict.has_key(((state_index), '$')):
          new_states += state_dict[((state_index), '$')]
          new_states = set(new_states)
       new_states = list(new_states)
    return new_states

Ovo je skup stanja:

q0,$->q2,q8
q2,a->q3
q3,$->q4
q4,$->q5
q4,a->q5
q5,$->q4,q6
q6,b->q7
q7,$->q1
q8,$->q10,q14
q9,$->q16    <-- dođemo do q9, dalje se ide u q16.
q10,b->q11
q11,$->q12
q12,c->q13
q13,$->q9     <-- ovdje krećemo, za svaki $ znak automatski se prelazi u navedeno stanje, ovdje je to q9.
q14,a->q15
q15,$->q9
q16,$->q17   <-- sad smo tu u q16, idemo dalje u q17
q16,c->q17
q17,$->q1,q16  <-- sad smo u q1 i  ponovno q16, ali dupli se ne računaju, vidimo da za q1 dalje ne postoji $ znak, pa smo gotovi.

E sad, ako definiram kao initial_state_fun stanje q13, funkcija bi trebala vratiti ['q13', 'q9', 'q16', 'q17', 'q1', 'q16'], ali vraća ['q13', 'q9', 'q16']. Nije mi jasno zašto stane kod stanja q16. Pretraživam po dictionary-u, key mi je oblika na primjer ('q13', '$'), a value je ['q9'] jer se on nalazi u ovoj tablici uz q13 i prijelaz $.

Eto, ako netko zna...samo mi još to fali...