如何设计识别(01∪001∪010)*的正确NFA与等价DFA？

a. 正确的NFA设计 #

目标语言是由01、001、010三个串任意重复连接（含空串）组成的集合。NFA需支持匹配这三个子串，完成匹配后回到起始状态以支持重复连接，同时起始状态设为终态以接受空串。

代码实现（基于automata.fa） #

from automata.fa.nfa import NFA

# 识别(01 ∪ 001 ∪ 010)*的NFA
correct_nfa = NFA(
    states={'q0', 'q1', 'q2', 'q3'},
    input_symbols={'0', '1'},
    transitions={
        'q0': {'0': {'q1'}},  # 起始状态读0进入q1，启动子串匹配
        'q1': {'1': {'q0', 'q3'}, '0': {'q2'}},  # 读1：要么完成01回到q0，要么进入q3准备匹配010；读0进入q2准备匹配001
        'q2': {'1': {'q0'}},  # 读1完成001，回到起始状态
        'q3': {'0': {'q0'}},  # 读0完成010，回到起始状态
    },
    initial_state='q0',
    final_states={'q0'}  # 起始状态为终态，接受空串；完成子串匹配后回到q0也接受
)

核心验证逻辑 #

• 匹配01：q0→q1→q0，到达终态，接受
• 匹配001：q0→q1→q2→q0，到达终态，接受
• 匹配010：q0→q1→q3→q0，到达终态，接受
• 匹配重复串如01001：q0→q1→q3→q0→q1→q2→q0，全程合法，接受

b. 等价DFA构造（仅可达部分） #

使用子集构造法将上述NFA转换为DFA，仅保留从起始状态可达的状态：

步骤1：定义DFA状态（对应NFA状态子集） #

• S0 = {q0}：起始状态，终态（包含NFA终态q0）
• S1 = {q1}：S0读0得到
• S2 = {q2}：S1读0得到
• S3 = {q0, q3}：S1读1得到，终态
• S4 = {q0, q1}：S3读0得到
• S5 = {q1, q2}：S4读0得到

DFA代码实现（基于automata.fa） #

from automata.fa.dfa import DFA

# 等价DFA（仅可达部分）
equivalent_dfa = DFA(
    states={'S0', 'S1', 'S2', 'S3', 'S4', 'S5'},
    input_symbols={'0', '1'},
    transitions={
        'S0': {'0': 'S1', '1': None},  # None表示无转移，直接拒绝
        'S1': {'0': 'S2', '1': 'S3'},
        'S2': {'0': None, '1': 'S0'},
        'S3': {'0': 'S4', '1': None},
        'S4': {'0': 'S5', '1': 'S3'},
        'S5': {'0': 'S2', '1': 'S3'}
    },
    initial_state='S0',
    final_states={'S0', 'S3'}  # 所有包含NFA终态q0的子集都是DFA终态
)

DFA状态说明 #

• S0：接受空串或完成一次子串匹配的状态
• S1：刚读入第一个0，等待后续字符匹配子串
• S2：读入00，等待读1完成001匹配
• S3：完成01匹配（回到q0），或读入01后等待读0完成010匹配
• S4：从S3读0后，同时处于可重新匹配的起始状态和继续匹配的中间状态
• S5：从S4读0后，同时处于两个中间匹配状态

内容的提问来源于stack exchange，提问作者DaneShuler