"""Original bounded DFA partition refinement, reachability and shortest distinguishing suffixes."""
from itertools import product,combinations
from collections import deque
import json

def minimize(trans,alphabet,start,accept):
 if not isinstance(trans,dict) or not 1<=len(trans)<=8 or not isinstance(alphabet,tuple) or not 1<=len(alphabet)<=3 or len(set(alphabet))!=len(alphabet) or any(type(a)!=str or len(a)!=1 for a in alphabet) or start not in trans or not isinstance(accept,set) or not accept<=set(trans) or any(not isinstance(row,dict) or set(row)!=set(alphabet) or any(q not in trans for q in row.values()) for row in trans.values()):raise ValueError('finite complete DFA')
 reachable={start};q=deque([start])
 while q:
  u=q.popleft()
  for a in alphabet:
   v=trans[u][a]
   if v not in reachable:reachable.add(v);q.append(v)
 blocks=[sorted(reachable-accept),sorted(reachable&accept)];blocks=sorted([b for b in blocks if b]);history=[blocks];signature_history=[]
 while True:
  owner={s:i for i,b in enumerate(blocks) for s in b};new=[];signature_history.append({s:[owner[trans[s][a]] for a in alphabet] for s in sorted(reachable)})
  for b in blocks:
   groups={}
   for s in b:groups.setdefault(tuple(owner[trans[s][a]] for a in alphabet),[]).append(s)
   new+=groups.values()
  new=sorted(map(sorted,new))
  if new==blocks:break
  blocks=new;history.append(blocks)
 owner={s:i for i,b in enumerate(blocks) for s in b};quotient={str(i):{a:str(owner[trans[b[0]][a]]) for a in alphabet} for i,b in enumerate(blocks)}
 for b in blocks:
  for s in b:
   for a in alphabet:assert owner[trans[s][a]]==owner[trans[b[0]][a]]
 return {'reachable':sorted(reachable),'removed_unreachable':sorted(set(trans)-reachable),'partition_history':history,'signature_history_by_alphabet':signature_history,'blocks':blocks,'quotient':quotient,'start':str(owner[start]),'accept':sorted(str(i) for i,b in enumerate(blocks) if set(b)&accept),'owner':owner}
def run(trans,start,word,accept):
 q=start
 for a in word:q=trans[q][a]
 return q in accept
def witness(trans,alphabet,p,q,accept):
 todo=deque([(p,q,'')]);seen={(p,q)}
 while todo:
  u,v,w=todo.popleft()
  if (u in accept)!=(v in accept):return w
  for a in alphabet:
   pair=(trans[u][a],trans[v][a])
   if pair not in seen:seen.add(pair);todo.append((*pair,w+a))
 return None

def demo():
 t={'S':{'a':'Z','b':'B'},'B':{'a':'W','b':'B'},'Z':{'a':'F','b':'B'},'W':{'a':'F','b':'B'},'F':{'a':'F','b':'B'},'U':{'a':'U','b':'U'}};alphabet=('a','b');accept={'F','U'};m=minimize(t,alphabet,'S',accept);assert m['blocks']==[['B','S'],['F'],['W','Z']] and m['removed_unreachable']==['U']
 checks=0
 for n in range(9):
  for chars in product(alphabet,repeat=n):
   word=''.join(chars);a=run(t,'S',word,accept);b=run(m['quotient'],m['start'],word,set(m['accept']));assert a==b==word.endswith('aa');checks+=1
 witnesses=[]
 for p,q in combinations(m['reachable'],2):
  suffix=witness(t,alphabet,p,q,accept);same=m['owner'][p]==m['owner'][q];assert (suffix is None)==same
  if suffix is not None:
   assert run(t,p,suffix,accept)!=run(t,q,suffix,accept)
   for n in range(len(suffix)):
    for chars in product(alphabet,repeat=n):assert run(t,p,''.join(chars),accept)==run(t,q,''.join(chars),accept)
  witnesses.append({'pair':[p,q],'same_block':same,'shortest_distinguishing_suffix':suffix})
 # Stable quotient homomorphism gives language preservation for all words; 511 words only additional finite test.
 bad=[]
 for label,fn in [('missing_transition',lambda:minimize({'S':{'a':'S'}},alphabet,'S',set())),('unknown_target',lambda:minimize({'S':{'a':'X','b':'S'}},alphabet,'S',set())),('unknown_accept',lambda:minimize(t,alphabet,'S',{'X'})),('unknown_start',lambda:minimize(t,alphabet,'X',accept)),('duplicate_symbol',lambda:minimize(t,('a','a'),'S',accept)),('budget',lambda:minimize({str(i):{'a':str(i),'b':str(i)} for i in range(9)},alphabet,'0',set()))]:
  try:fn()
  except ValueError:bad.append(label)
  else:raise AssertionError(label)
 return {'original_transition':t,'alphabet':alphabet,'original_accept':sorted(accept),'minimization':m,'finite_word_checks':checks,'all_reachable_pair_suffix_certificates':witnesses,'invalid_cases_rejected':bad,'scope':'Own complete finite DFA, remove unreachable before refinement, stable partition transition homomorphism and distinct-block suffix certificates.511 finite tests not proof allwords on their own. Not Hopcroft complexity/NFA/regex engine/product parser.'}
if __name__=='__main__':print(json.dumps(demo(),indent=2))