Encountering some trouble while comparing equal status:
It's not equal while a status is in ending states , and another one is not in ending stats:
Fixed with coming codes:
def minimise(self):
states = list(self.dfa.states)
n = len(states)
unchecked = dict()
count = 1
distinguished = []
equivalent = dict(zip(range(len(states)), [{s} for s in states]))
pos = dict(zip(states, range(len(states))))
for i in range(n - 1):
for j in range(i + 1, n):
if not ([states[i], states[j]] in distinguished or [states[j], states[i]] in distinguished):
if (states[i] in self.dfa.finalstates and states[j] not in self.dfa.finalstates) or (states[i] not in self.dfa.finalstates and states[j] in self.dfa.finalstates):
distinguished.append([states[i], states[j]])
continue
eq = 1
toappend = []
for char in self.dfa.language:
s1 = self.dfa.gettransitions(states[i], char)
print "debug trans "
print s1
s2 = self.dfa.gettransitions(states[j], char)
if len(s1) != len(s2):
eq = 0
break
if len(s1) > 1:
raise BaseException("Multiple transitions detected in DFA")
elif len(s1) == 0:
continue
s1 = s1.pop()
s2 = s2.pop()
if s1 != s2:
if [s1, s2] in distinguished or [s2, s1] in distinguished:
eq = 0
break
else:
toappend.append([s1, s2, char])
eq = -1
if eq == 0:
distinguished.append([states[i], states[j]])
elif eq == -1:
s = [states[i], states[j]]
s.extend(toappend)
unchecked[count] = s
count += 1
else:
p1 = pos[states[i]]
p2 = pos[states[j]]
if p1 != p2:
st = equivalent.pop(p2)
for s in st:
pos[s] = p1
equivalent[p1] = equivalent[p1].union(st)
newFound = True
while newFound and len(unchecked) > 0:
newFound = False
toremove = set()
for p, pair in unchecked.items():
for tr in pair[2:]:
if [tr[0], tr[1]] in distinguished or [tr[1], tr[0]] in distinguished:
unchecked.pop(p)
distinguished.append([pair[0], pair[1]])
newFound = True
break
for pair in unchecked.values():
p1 = pos[pair[0]]
p2 = pos[pair[1]]
if p1 != p2:
st = equivalent.pop(p2)
for s in st:
pos[s] = p1
equivalent[p1] = equivalent[p1].union(st)
if len(equivalent) == len(states):
self.minDFA = self.dfa
else:
self.minDFA = self.dfa.newBuildFromEquivalentStates(equivalent, pos)
Encountering some trouble while comparing equal status: It's not equal while a status is in ending states , and another one is not in ending stats: Fixed with coming codes: