正则表达式与FA的等价

### 正则表达式与有限自动机的等价性

正则表达式（Regular Expression, RE）和有限自动机（Finite Automaton, FA），无论是确定型有限自动机（DFA）还是非确定型有限自动机（NFA），都具有相同的计算能力，即它们能够描述同一类语言——正规语言。

#### 从正则表达式到有限自动机构造

对于任何给定的正则表达式 \( r \)，可以构建一个对应的非确定型有限自动机 \( M_r \) 来接受由该正则表达式所定义的语言。这一过程可以通过 Thompson 构造法实现[^1]：

- 对于基础情况下的简单字符 \( a \in Σ \)，可以直接创建两个状态并用标记为 \( a \) 的边连接起来。
- 当遇到更复杂的结构时，比如串联、选择或闭包操作符，则相应地组合多个这样的基本单元形成更大的模式匹配机制。

def thompson Construction(r):
    if isinstance(r, str):  # 单个字符的情况
        start_state = State()
        end_state = State()
        transition(start_state, end_state, symbol=r)
        return NFA(start=start_state, accept=end_state)

    elif r.type == 'concat':  # 连接运算
        nfa_left = thompson_construction(r.left)
        nfa_right = thompson_construction(r.right)
        connect(nfa_left.accept, nfa_right.start)
        return NFA(start=nfa_left.start, accept=nfa_right.accept)

    elif r.type == 'union':  # 或者/选择运算
        start_state = State()
        end_state = State()
        nfa_left = thompson_construction(r.left)
        nfa_right = thompson_construction(r.right)
        epsilon_transition(start_state, nfa_left.start)
        epsilon_transition(start_state, nfa_right.start)
        epsilon_transition(nfa_left.accept, end_state)
        epsilon_transition(nfa_right.accept, end_state)
        return NFA(start=start_state, accept=end_state)

    elif r.type == 'closure':  # 星号闭包运算
        start_state = State()
        end_state = State()
        inner_nfa = thompson_construction(r.inner)
        epsilon_transition(start_state, inner_nfa.start)
        epsilon_transition(inner_nfa.accept, start_state)
        epsilon_transition(start_state, end_state)
        epsilon_transition(end_state, inner_nfa.start)
        return NFA(start=start_state, accept=end_state)

#### 从有限自动机到正则表达式的转化

另一方面，也可以通过消除中间节点的方法将任意形式的 DFA 转换成相应的正则表达式。此方法涉及逐步删除除起始状态外的所有其他内部状态，并更新剩余路径上的标签以保持原始行为不变[^3]。

具体来说就是不断寻找那些既不是初始也不是终止的状态作为候选对象进行移除；每当去除某个特定顶点 v 后，需要调整其相邻两点 u 和 w 之间可能存在的新转移关系来补偿因失去中介而丢失的信息流传递特性。

这种双向映射的存在表明了两者间存在内在联系以及彼此可互换使用的可能性，从而确立了二者在理论上的一致性和功能性上的互补作用。