将正则表达式转化为nfa再转化为dfa

### 正则表达式转NFA 正则表达式的每一个操作符都可以映射成特定结构的有限自动机。对于基本字符a，可以构建一个简单的两状态NFA M(a)，其中有一个从起始状态指向接受状态的标记为a的转移弧[^1]。 当遇到更复杂的正则表达式时，可以通过组合这些基础单元来创建对应的NFA： - 对于连接运算ab，先建立M(a)再建立M(b), 并将前者的目标节点与后者源节点相接合形成新的机器。 - 针对选择运算\( a|b \)，分别构造两个子模式各自的NFA Mi, 然后引入一个新的初始态通过ε-moves通往各Mi入口；同样地，在所有终点之后附加额外的状态作为共同结束点。 - 关于闭包运算\( a* \)，即零次或多次重复某个元素，则需设计循环路径允许任意数量遍历该部分图案[^2]. ```python import re from thompson import compile # 假设thompson是一个实现了上述算法的库 pattern = 'abc' nfa = compile(re.compile(pattern)) ``` ### NFA 转 DFA 由非确定性有穷自动机(NFA)向确定性有穷自动机(DFA)转变的过程通常采用子集构造法(Subset Construction Algorithm): 此过程始于计算NFAs start state 的 ε-closure (包含所有可通过空串到达的状态集合)[^3]. 接着针对每个尚未处理过的DFA状态S及其输入符号c: - 计算 move(S,c)=T ，这里 T 表示从 S 中任一成员经 c 达到的一组新位置； - 扩展得到 E(T)，也就是加入任何能仅靠 epsilon 过渡访问的位置； - 如果E(T)还未被记录为现有DFA的一个状态，则新增之并继续探索直至无未考察项为止. 最终获得完全定义好的最小化后的DFA能够模拟原始NFA的行为特征而无需回溯或者猜测下一步行动方向[^4]. ```python def nfa_to_dfa(nfa): dfa_states = [] transitions = {} # Start with the epsilon closure of the NFA's initial state as our first DFA state. current_state = epsilon_closure({nfa.start}) unprocessed_states = [current_state] while unprocessed_states: processing_state = unprocessed_states.pop() if processing_state not in dfa_states: dfa_states.append(processing_state) for symbol in alphabet: next_states = set() for state in processing_state: if state in nfa.transitions and symbol in nfa.transitions[state]: next_states.update(nfa.transitions[state][symbol]) ec_next_states = epsilon_closure(next_states) if ec_next_states and ec_next_states not in dfa_states: unprocessed_states.append(ec_next_states) transition_key = frozenset(processing_state), symbol if transition_key not in transitions or \ (transition_key in transitions and len(transitions[transition_key]) < len(ec_next_states)): transitions[transition_key] = ec_next_states return {'states':dfa_states,'transitions':transitions} ```