XGH_DFA_minimization.py

# 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)