编译原理自动机的确定化和最小化

### 编译原理中的自动机确定化与最小化

#### 不确定有穷自动机(NFA)转换为确定有穷自动机(DFA)

正则表达式的处理通常涉及将其转化为不确定有穷自动机（NFA），再进一步转化成确定有穷自动机（DFA）。对于给定的正则表达式 \( r=(a|b)^*abb \)，首先构建其对应的NFA[^1]。

为了实现这一过程，采用子集构造法可以有效地将NFA转变为等价的DFA。该算法的核心在于通过计算ε闭包以及针对每个输入符号扩展这些集合来逐步建立新的状态及其转移函数[^2]。

def nfa_to_dfa(nfa_states, nfa_transitions, start_state, final_states):
    dfa_states = []
    dfa_transitions = {}
    
    unprocessed_sets = [{start_state}]
    processed_sets = set()
    
    while unprocessed_sets:
        current_set = unprocessed_sets.pop(0)
        if frozenset(current_set) not in processed_sets:
            for symbol in symbols:
                next_set = compute_epsilon_closure(move(current_set, symbol))
                
                if next_set and next_set not in dfa_states:
                    unprocessed_sets.append(next_set)
                    
                add_transition(dfa_transitions, current_set, symbol, next_set)
            
            processed_sets.add(frozenset(current_set))
            dfa_states.append(current_set)
        
    return dfa_states, dfa_transitions

此代码片段展示了如何利用Python实现从NFA向DFA转变的过程，其中`compute_epsilon_closure()`用于获取指定状态下所有可达的状态集合，而`move()`负责根据当前状态和输入符号找到下一个可能达到的状态集合。

#### DFA最小化

一旦获得了DFA，则可以通过一系列步骤对其进行简化以减少冗余状态数量而不改变其所能接受的语言。这涉及到识别并合并那些行为完全相同的不可区分状态。具体操作如下：

- **初始分割**：把所有状态分为两类——终止状态和非终止状态。
- **细化分区**：迭代地检查每一对不同组内的状态\( s_i \) 和 \( s_j \)，如果它们在遇到某些特定输入后转移到不同的分区内，则应分开这两者；反之保持在同一类内直到不再发生变化为止[^3]。

最终得到的是一个具有最少必要状态数目但仍能够执行相同功能的新版本DFA。