Created
January 21, 2018 22:32
-
-
Save tysm/2072d81ef455b6b894fb69fe6793e5eb to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# conding: utf-8 | |
""" | |
Código de minimização de autômatos finitos determinísticos incompletos ou completos | |
Autor: Thalles Medrado | |
21/01/2018 | |
""" | |
def ipt(): | |
return int(input()) | |
class AFD_t(): | |
def __init__(self, Q, A, qi, F): | |
self.Q = Q | |
self.A = A | |
self.qi = qi | |
self.F = F | |
class q_t(): | |
def __init__(self, i): | |
self.i = i | |
self.S = {} | |
alcancavel = {} | |
def percorre(M, q): | |
if alcancavel[M.Q[q]]: | |
return | |
alcancavel[M.Q[q]] = True | |
for a in M.A: | |
if a not in M.Q[q].S: | |
continue | |
percorre(M, M.Q[q].S[a]) | |
def remove_inalcancavel(M): | |
lenMQ = len(M.Q) | |
global alcancavel | |
alcancavel = {q: False for q in M.Q} | |
alcancavel[M.Q[M.qi]] = True | |
for a in M.A: | |
if a not in M.Q[M.qi].S: | |
continue | |
percorre(M, M.Q[M.qi].S[a]) | |
for q in alcancavel: | |
if not alcancavel[q]: | |
if q.i in M.F: | |
M.F.remove(q.i) | |
M.Q.remove(q) | |
Mrange = set(range(len(M.Q))) | |
M.F = list(M.F) | |
for q in Mrange: | |
if M.Q[q].i!=q: | |
if M.qi==M.Q[q].i: | |
M.qi = q | |
if M.Q[q].i in M.F: | |
M.F.remove(M.Q[q].i) | |
M.F.append(q) | |
for ql in Mrange: | |
for a in M.A: | |
if a not in M.Q[ql].S: | |
continue | |
if M.Q[ql].S[a]==M.Q[q].i: | |
M.Q[ql].S[a] = q | |
M.Q[q].i = q | |
M.F = set(M.F) | |
def completa(M): | |
lenMQ = len(M.Q) | |
lenMA = len(M.A) | |
completo = True | |
for i in range(lenMQ): | |
if len(M.Q[i].S)!=lenMA: | |
completo = False | |
break | |
if completo: | |
return | |
M.Q.append(q_t(lenMQ)) | |
for i in range(lenMQ+1): | |
if len(M.Q[i].S)==lenMA: | |
continue | |
for a in M.A: | |
if a not in M.Q[i].S: | |
M.Q[i].S[a] = lenMQ | |
def minimiza(M): | |
Mrange = set(range(len(M.Q))) | |
EQ = [[True for j in Mrange] for i in Mrange] | |
for q in Mrange-M.F: | |
for qf in M.F: | |
EQ[q][qf] = EQ[qf][q] = False | |
mudou = True | |
while mudou: | |
mudou = False | |
for q in Mrange: | |
for ql in range(q): | |
if EQ[q][ql]: # same of EQ[ql][q] | |
for a in M.A: | |
if a not in M.Q[q].S or a not in M.Q[ql].S: | |
continue | |
qll = M.Q[q].S[a] | |
qlll = M.Q[ql].S[a] | |
if not EQ[qll][qlll]: # same of EQ[qlll][qll] | |
EQ[q][ql] = EQ[ql][q]=False | |
mudou = True | |
break | |
for q in Mrange: | |
EQ[q][q] = False | |
garbage = {} | |
for i in Mrange: | |
for j in range(i): | |
if not EQ[i][j]: # same of EQ[j][i] | |
continue | |
q = i | |
ql = j | |
while q in garbage: | |
q = garbage[q][0] | |
while ql in garbage: | |
ql = garbage[ql][0] | |
# safaty | |
if not EQ[q][ql]: # same of EQ[ql][q] | |
continue | |
qll = min(q, ql) | |
if q in M.F or ql in M.F: | |
try: | |
M.F.remove(q) | |
except: | |
pass | |
try: | |
M.F.remove(ql) | |
except: | |
pass | |
M.F.add(qll) | |
if q==M.qi or ql==M.qi: | |
M.qi = qll | |
for a in M.A: | |
""" | |
# error here | |
e=M.Q[q].S[a] | |
el=M.Q[ql].S[a] | |
if e==q or e==ql or el==q or el==ql: | |
M.Q[qll].S[a]=qll | |
""" | |
for e in Mrange: | |
if a not in M.Q[e].S: | |
continue | |
el = M.Q[e].S[a] | |
if el==q or el==ql: | |
M.Q[e].S[a] = qll | |
if q!=qll: | |
garbage[q] = (qll, M.Q[q]) | |
else: | |
garbage[ql] = (qll, M.Q[ql]) | |
EQ[i][j] = EQ[j][i] = False | |
EQ[q][ql] = EQ[ql][q] = False | |
for key in garbage.keys(): | |
M.Q.remove(garbage[key][1]) | |
Mrange = set(range(len(M.Q))) | |
M.F = list(M.F) | |
for q in Mrange: | |
if M.Q[q].i!=q: | |
if M.qi==M.Q[q].i: | |
M.qi = q | |
if M.Q[q].i in M.F: | |
M.F.remove(M.Q[q].i) | |
M.F.append(q) | |
for ql in Mrange: | |
for a in M.A: | |
if a not in M.Q[ql].S: | |
continue | |
if M.Q[ql].S[a]==M.Q[q].i: | |
M.Q[ql].S[a] = q | |
M.Q[q].i = q | |
M.F = set(M.F) | |
if __name__ == "__main__": | |
n = ipt() # n estados q0, ..., qn-1 | |
Q = [q_t(i) for i in range(n)] | |
m = ipt() # m símbolos a0, ..., am-1 | |
A = [i for i in range(m)] | |
qi = ipt() # estado inicial | |
l = ipt() # l estados finais qn1, ..., qnl | |
F = {int(i) for i in input().split(",")} | |
t = ipt() # t triplas | |
for i in range(t): | |
tripla = input().split(",") | |
Q[int(tripla[0])].S[int(tripla[1])] = int(tripla[2]) | |
M = AFD_t(Q, A, qi, F) | |
remove_inalcancavel(M) | |
#completa(M) | |
minimiza(M) | |
rn = len(M.Q) | |
rm = len(M.A) | |
rqi = M.qi | |
rl = len(M.F) | |
rF = str() | |
M.F = list(M.F) | |
for i in range(rl): | |
if i: | |
rF+=", " | |
rF+=str(M.F[i]) | |
M.F = set(M.F) | |
rt = 0 | |
rtriplas = [] | |
for i in range(rn): | |
for key in M.Q[i].S.keys(): | |
rt+=1 | |
rtriplas.append(str(i) + ", " + str(key) + ", " + str(M.Q[i].S[key])) | |
print(rn) | |
print(rm) | |
print(rqi) | |
print(rl) | |
print(rF) | |
print(rt) | |
for rtripla in rtriplas: | |
print(rtripla) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment