"""W07: a complete DFA comparison, not an arbitrary program-equivalence solver."""
from collections import deque
def validate(machine,alphabet):
if type(machine) is not dict or set(machine)!={'states','start','accept','transition'}:
raise ValueError("wrong DFA schema")
n=machine['states']
if type(n) is not int or not 1<=n<=100 or type(machine['start']) is not int or not 0<=machine['start']<n:
raise ValueError("bounded state count and valid start required")
if any(type(q) is not int or not 0<=q<n for q in machine['accept']):raise ValueError("bad accepting state")
expected={(q,a) for q in range(n) for a in alphabet}
if set(machine['transition'])!=expected:raise ValueError("complete transition table required")
if any(type(q) is not int or not 0<=q<n for q in machine['transition'].values()):raise ValueError("bad target")
def distinguishing_word(left,right,alphabet=('a','b')):
alphabet=tuple(alphabet)
if not alphabet or len(set(alphabet))!=len(alphabet) or any(type(a) is not str or len(a)!=1 for a in alphabet):
raise ValueError("unique one-character alphabet symbols required")
validate(left,alphabet);validate(right,alphabet)
start=(left['start'],right['start'])
parent={start:None};todo=deque([start])
while todo:
pair=todo.popleft()
if (pair[0] in left['accept']) != (pair[1] in right['accept']):
symbols=[]
while parent[pair] is not None:
previous,symbol=parent[pair];symbols.append(symbol);pair=previous
return ''.join(reversed(symbols))
for symbol in alphabet:
nxt=(left['transition'][pair[0],symbol],right['transition'][pair[1],symbol])
if nxt not in parent:
parent[nxt]=pair,symbol;todo.append(nxt)
return None
def accepts(machine,word):
state=machine['start']
for symbol in word:state=machine['transition'][state,symbol]
return state in machine['accept']
if __name__=='__main__':
even={'states':2,'start':0,'accept':{0},
'transition':{(0,'a'):1,(1,'a'):0,(0,'b'):0,(1,'b'):1}}
everything={'states':1,'start':0,'accept':{0},'transition':{(0,'a'):0,(0,'b'):0}}
print(repr(distinguishing_word(even,everything)))