Изменения

# * Обращение КА

def fa_rev(fa): rfa = [list(fa[Q]), list(fa[A]), [], list(fa[F]), list(fa[S])] rfa[T] = [[[] for i in range(0, len(fa[A]))] for j in range(0, len(fa[Q]))] for t1 in range(0, len(fa[Q])): for a in range(0, len(fa[A])): for t2 in fa[T][t1][a]: rfa[T][t2][a].append(t1) return rfa

# * Детерминизация КА

def fa_det(fa): def reachable(q, l): t = [] for a in range(0, len(fa[A])): ts = set() for i in q[l]: # объединение множеств (достижимых из l) состояний для символа a ts |= set(fa[T][i][a]) if not ts: t.append([]) continue try: i = q.index(ts) except ValueError: i = len(q) q.append(ts) t.append([i]) return t dfa = [[], list(fa[A]), [], [0], []] q = [set(fa[S])] while len(dfa[T]) < len(q): dfa[T].append(reachable(q, len(dfa[T]))) dfa[Q] = range(0, len(q)) dfa[F] = [q.index(i) for i in q if set(fa[F]) & i] return dfa

# * Алгоритм Бржозовского

def fa_min(fa): return fa_det(fa_rev(fa_det(fa_rev(fa))))