### 实现NFA到DFA的确定化及自动机最小化的Python代码 #### NFA转DFA的过程 为了实现从非确定有限状态自动机(NFA)向确定有限状态自动机(DFA)转变，通常采用子集构造算法。此过程涉及创建一个新的初始状态集合，该集合由原NFA的所有可能ε-closure(即可以从起始位置经零步或多步ε移动到达的状态)[^1]组成。 对于每一个新产生的DFA状态（实际上是NFA状态的一个集合），针对字母表中的每个字符计算其对应的下一组可达状态，并将其作为一个新的DFA状态加入到正在构建的新机器中去。如果这个组合之前已经遇到过，则不再重复添加而是指向已存在的对应节点。整个流程持续直到所有可访问的状态都被处理完毕为止[^2]。 ```python from collections import defaultdict, deque def epsilon_closure(nfa_states, nfa_transitions): closure = set() stack = list(nfa_states) while stack: state = stack.pop() if state not in closure: closure.add(state) if 'eps' in nfa_transitions[state]: stack.extend(nfa_transitions[state]['eps']) return frozenset(closure) def move(states, symbol, transitions): result = set() for state in states: if symbol in transitions[state]: result.update(transitions[state][symbol]) return frozenset(result) def subset_construction(nfa_start_state, nfa_accepting_states, nfa_transitions, alphabet): dfa_states = {} queue = deque([epsilon_closure({nfa_start_state}, nfa_transitions)]) start_dfa_state = next(iter(queue)) accepting_states = [] transition_table = {} while queue: current_set_of_nfa_states = queue.popleft() # Mark the DFA state as visited and check acceptance. index = len(dfa_states) dfa_states[current_set_of_nfa_states] = index if any(s in nfa_accepting_states for s in current_set_of_nfa_states): accepting_states.append(index) new_transitions = {s: None for s in alphabet} for a in alphabet: moved = move(current_set_of_nfa_states, a, nfa_transitions) eps_closed_moved = epsilon_closure(moved, nfa_transitions) if eps_closed_moved not in dfa_states: queue.append(eps_closed_moved) new_transitions[a] = dfa_states.get(eps_closed_moved, None) transition_table[index] = new_transitions return { "start": dfa_states[start_dfa_state], "accepting": accepting_states, "transitions": transition_table } ``` 上述函数实现了基于给定NFA定义(`nfa_start_state`, `nfa_accepting_states` 和 `nfa_transitions`)来生成相应的DFA结构体。这里特别注意到了ε-闭包的概念，在某些情况下需要考虑ε迁移的存在[^3]。 #### 自动机最小化 一旦获得了完整的DFA描述之后，就可以继续执行最小化操作以消除冗余状态并简化模型： ```python def minimize_dfa(dfa): marked_pairs = set() # Pairs of distinguishable states (p,q). unmarked_pairs = [] # List to hold pairs that need checking. # Initially mark all pairs where one is final and other isn't. for p in range(len(dfa["states"])): for q in range(p + 1, len(dfa["states"])): if ((dfa["is_final"][p] != dfa["is_final"][q])): marked_pairs.add((min(p, q), max(p, q))) else: unmarked_pairs.append((p, q)) changed = True while changed: changed = False temp_unmarked = [] for pair in unmarked_pairs: p, q = sorted(pair) should_mark = False for char in dfa['alphabet']: target_p = dfa["transitions"].get((p, char)) or -1 target_q = dfa["transitions"].get((q, char)) or -1 if target_p >= 0 and target_q >= 0 and \ tuple(sorted((target_p, target_q))) in marked_pairs: should_mark = True break if should_mark: marked_pairs.add(tuple(sorted(pair))) changed = True else: temp_unmarked.append(pair) unmarked_pairs[:] = temp_unmarked[:] equivalent_classes = {} # Map from original state id -> class representative. classes = [[]] # Classes are lists within this outer list. for i in range(len(dfa["states"])): found_class = False for cls in classes: rep = cls[0] can_be_in_same_class = True for ch in dfa['alphabet']: trans_i = dfa["transitions"].get((i, ch)) or -1 trans_rep = dfa["transitions"].get((rep, ch)) or -1 if trans_i >= 0 and trans_rep >= 0 and \ tuple(sorted((trans_i, trans_rep))) in marked_pairs: can_be_in_same_class = False break if can_be_in_same_class: cls.append(i) equivalent_classes[i] = rep found_class = True break if not found_class: classes.append([i]) equivalent_classes[i] = i minimized_transitions = {} minimized_is_final = [False]*len(classes) mapping = {} for old_id, eqv_cls in enumerate(classes): new_id = len(mapping) mapping[eqv_cls[0]] = new_id for st in eqv_cls: minimized_is_final[new_id] |= dfa["is_final"][st] for sym in dfa['alphabet']: dest_old = dfa["transitions"].get((eqv_cls[0], sym)) if dest_old is not None: dest_new = mapping[equivalent_classes[dest_old]] minimized_transitions[(new_id, sym)] = dest_new return {"states": list(range(len(minimized_is_final))), "initial": min(equivalent_classes.values()), "final": [idx for idx,val in enumerate(minimized_is_final) if val], "transitions": minimized_transitions} ``` 这段代码展示了如何利用划分细化的方法来进行DFA最小化。它首先标记那些可以直接区分出来的状态对，接着迭代地寻找更多可以通过观察它们在不同输入下的行为差异而被区分开来的状态对。最后根据这些信息重新组织状态空间，形成更紧凑的形式[^4]。