<s> class FiniteAutomaton : <EOL> def __init__ ( self , start_state , dump_state = '<STR_LIT>' ) : <EOL> self . start_state = start_state <EOL> self . dump_state = dump_state <EOL> self . table = { self . dump_state : { } } <EOL> self . unresolved_composites = [ ] <EOL> self . resolved_composites = [ ] <EOL> self . composite_memo = { } <EOL> self . is_updated = <NUM_LIT:1> <EOL> def __setitem__ ( self , ( state , symbol ) , x ) : <EOL> self . table . setdefault ( state , { } ) [ symbol ] = x <EOL> self . is_updated = <NUM_LIT:1> <EOL> def add_transition ( self , state , symbol , * nexts ) : <EOL> if len ( nexts ) == <NUM_LIT:1> : <EOL> c = nexts [ <NUM_LIT:0> ] <EOL> else : <EOL> for n in nexts : <EOL> if n not in self . table : <EOL> self . table [ n ] = { } <EOL> c = self . new_composite ( nexts ) <EOL> self [ state , symbol ] = c <EOL> if c not in self . table : <EOL> self . table [ c ] = { } <EOL> def get_row_items ( self , state ) : <EOL> try : <EOL> x = self . table [ state ] . items ( ) <EOL> except KeyError : <EOL> return ( ) <EOL> ris = [ ] <EOL> for k , v in x : <EOL> if isinstance ( v , CompositeState ) : <EOL> for vi in v : <EOL> ris . append ( ( k , vi ) ) <EOL> else : <EOL> ris . append ( ( k , v ) ) <EOL> return ris <EOL> def make_deterministic ( self ) : <EOL> while self . unresolved_composites : <EOL> composites = self . unresolved_composites <EOL> self . unresolved_composites = [ ] <EOL> for c in composites : <EOL> ds = { } <EOL> l = [ ] <EOL> for a in c : <EOL> for k , v in self . get_row_items ( a ) : <EOL> ds . setdefault ( k , [ ] ) . append ( v ) <EOL> for k , v in ds . items ( ) : <EOL> for a in c : <EOL> if k not in self . table [ a ] : <EOL> v . append ( self . dump_state ) <EOL> break <EOL> for k , v in ds . items ( ) : <EOL> self . add_transition ( c , k , * v ) <EOL> def get_all_input_symbols ( self ) : <EOL> syms = { } <EOL> for state , trans in self . table . items ( ) : <EOL> for k , v in trans : <EOL> syms [ k ] = <NUM_LIT:1> <EOL> return syms <EOL> def get_all_states ( self ) : <EOL> return self . table <EOL> def get_all_final_states ( self ) : <EOL> return { } <EOL> def get_composites ( self ) : <EOL> if self . is_updated : <EOL> self . make_deterministic ( ) <EOL> return self . composite_memo . values ( ) <EOL> def get_transition_classes ( self ) : <EOL> tc = { } <EOL> tck = { } <EOL> for k , v in self . table . items ( ) : <EOL> trans = v . keys ( ) <EOL> trans . sort ( ) <EOL> trans = tuple ( trans ) <EOL> ks = tc . get ( trans ) <EOL> if ks is None : <EOL> ks = [ ] <EOL> tc [ trans ] = ks <EOL> ks . append ( k ) <EOL> tck [ k ] = ks <EOL> return tc , tck <EOL> def get_minimized_dfa ( self , finals ) : <EOL> def markall ( finals , tcv , table ) : <EOL> def psrmark ( l ) : <EOL> for pq in l : <EOL> if pq in PS : <EOL> l1 = PS [ pq ] <EOL> del PS [ pq ] <EOL> if l1 : <EOL> psrmark ( l1 ) <EOL> PS = { } <EOL> for Q in tcv : <EOL> for ip , p in enumerate ( Q ) : <EOL> for q in Q [ ip + <NUM_LIT:1> : ] : <EOL> if ( p in finals ) == ( q in finals ) : <EOL> PS [ ( p , q ) ] = ( ) <EOL> for pq in PS . keys ( ) : <EOL> p , q = pq <EOL> dp = table [ p ] <EOL> dq = table [ q ] <EOL> dps = [ ] <EOL> for a in dp : <EOL> dpa = dp [ a ] <EOL> dqa = dq [ a ] <EOL> if dpa is not dqa : <EOL> dpadqa = ( dpa , dqa ) <EOL> if dpadqa in PS : <EOL> dps . append ( dpadqa ) <EOL> else : <EOL> dqadpa = ( dqa , dpa ) <EOL> if dqadpa in PS : <EOL> dps . append ( dqadpa ) <EOL> else : <EOL> l = PS [ pq ] <EOL> del PS [ pq ] <EOL> if l is not ( ) : <EOL> psrmark ( l ) <EOL> break <EOL> else : <EOL> for dpadqa in dps : <EOL> l = PS [ dpadqa ] <EOL> if l is ( ) : <EOL> l = [ pq ] <EOL> PS [ dpadqa ] = l <EOL> else : <EOL> l . append ( pq ) <EOL> return PS <EOL> def combine ( QS , PQS ) : <EOL> eqs = { } <EOL> for Q in QS : <EOL> for p in Q : <EOL> eqs [ p ] = [ p ] <EOL> for p , q in PQS : <EOL> ep = eqs [ p ] <EOL> eq = eqs [ q ] <EOL> if eq is not ep : <EOL> if len ( eq ) > len ( ep ) : <EOL> eq , ep = ep , eq <EOL> ep . extend ( eq ) <EOL> for q in eq : <EOL> eqs [ q ] = ep <EOL> return eqs <EOL> def finalize ( eqs ) : <EOL> csbyid = { } <EOL> csbyas = { } <EOL> i = <NUM_LIT:0> <EOL> for eq in eqs . values ( ) : <EOL> ideq = id ( eq ) <EOL> if ideq not in csbyid : <EOL> c = '<STR_LIT>' % i <EOL> i += <NUM_LIT:1> <EOL> csbyid [ ideq ] = eq [ <NUM_LIT:0> ] , c <EOL> for s in eq : <EOL> csbyas [ s ] = c <EOL> fsa = self . __class__ ( csbyas [ self . start_state ] ) <EOL> fsa . final_states = { } <EOL> for cs0 , cst in csbyid . values ( ) : <EOL> fsa . table [ cst ] = trans = { } <EOL> for a , s in self . table [ cs0 ] . items ( ) : <EOL> trans [ a ] = csbyas [ s ] <EOL> if cs0 in finals : <EOL> fsa . final_states [ cst ] = <NUM_LIT:1> <EOL> return fsa <EOL> if self . is_updated : <EOL> self . make_deterministic ( ) <EOL> tctck = self . _tctck = self . get_transition_classes ( ) <EOL> self . is_updated = <NUM_LIT:0> <EOL> else : <EOL> tctck = self . _tctck <EOL> tc , tck = tctck <EOL> tcv = tc . values ( ) <EOL> PS = markall ( finals , tcv , self . table ) <EOL> eqs = combine ( tcv , PS ) <EOL> fsa = finalize ( eqs ) <EOL> return fsa <EOL> def new_composite ( self , args ) : <EOL> cs = CompositeState ( dict ( [ ( arg , <NUM_LIT:1> ) for arg in args ] ) . keys ( ) ) <EOL> if len ( cs ) == <NUM_LIT:1> : <EOL> return args [ <NUM_LIT:0> ] <EOL> try : <EOL> return self . composite_memo [ cs ] <EOL> except KeyError : <EOL> self . composite_memo [ cs ] = cs <EOL> self . unresolved_composites . append ( cs ) <EOL> return cs <EOL> def pp ( self ) : <EOL> ks = self . table . keys ( ) <EOL> ks . sort ( ) <EOL> num = dict ( [ ( s , i ) for i , s in enumerate ( ks ) ] ) <EOL> for s in ks : <EOL> k = self . table [ s ] <EOL> print '<STR_LIT>' % ( num [ s ] , s ) <EOL> cs = k . keys ( ) <EOL> cs . sort ( ) <EOL> for c in cs : <EOL> v = k [ c ] <EOL> print '<STR_LIT>' % ( c , num [ v ] , v ) <EOL> class CompositeState ( tuple ) : <EOL> pass </s>
