正则语言星闭包NFA构造错误排查：基于定理1.49的实现问题

我学习了定理1.49（正则语言类在星运算下封闭）的NFA构造方法：添加一个新的既是起始又是接受的状态，通过ε转换连接到原自动机的起始状态；同时为原自动机的所有接受状态添加ε转换回新起始状态，以此识别语言的星闭包（包含空串ε）。

构造的两个星闭包NFA及测试失败情况 #

1. 针对1.6a的NFA构造星闭包NFA #

原1.6a的NFA代码：

prob_1_6a = NFA(
    states={'0', '1', '3', '2'},
    input_symbols={'0', '1'},
    transitions={'0': {'0': {'3'}, '1': {'1'}}, '1': {'1': {'1'}, '0': {'2'}}, '2': {'0': {'2'}, '1': {'1'}}, '3': {}},
    initial_state='0',
    final_states={'2'}
)

我构造的星闭包NFA：

prob_1_10d = NFA(
    states={'0', '1', '2', '3', 'start'},  # 添加新起始状态
    input_symbols={'0', '1'},
    transitions={
        'start': {'': {'0'}},  # 从新起始状态到原起始状态的ε转换
        '0': {'0': {'3'}, '1': {'1'}, '': {'start'}},  # 添加回新起始状态的ε转换用于Kleene星
        '1': {'1': {'1'}, '0': {'2'}, '': {'start'}},  # 添加回新起始状态的ε转换用于Kleene星
        '2': {'0': {'2'}, '1': {'1'}, '': {'start'}},  # 添加回新起始状态的ε转换用于Kleene星
        '3': {'': {'start'}}  # 添加回新起始状态的ε转换用于Kleene星
    },
    initial_state='start',  # 带ε转换的新起始状态
    final_states={'start'}  # 仅新起始状态为接受状态
)

2. 针对1.6k的DFA构造星闭包NFA #

原1.6k的DFA代码：

prob_1_6k = DFA(
    states={'q0', 'q1', 'q2'},
    input_symbols={'0', '1'},
    transitions={
        'q0': {'0': 'q1', '1': 'q2'},
        'q1': {'0': 'q2', '1': 'q2'},
        'q2': {'0': 'q2', '1': 'q2'}
    },
    initial_state='q0',
    final_states={'q0', 'q1'}
)

我构造的星闭包NFA：

prob_1_10e = NFA(
    states={'0', '1', '2', '3', 'start'},  # 原状态加Kleene星的新起始状态
    input_symbols={'0', '1'},
    transitions={
        'start': {'': {'0', 'start'}},  # 到原起始状态和自身的ε转换
        '0': {'0': {'3'}, '1': {'1'}, '': {'start'}},  # 到新起始状态的ε转换
        '1': {'0': {'2'}, '1': {'1'}, '': {'start'}},  # 到新起始状态的ε转换
        '2': {'0': {'2'}, '1': {'1'}, '': {'start'}},  # 到新起始状态的ε转换
        '3': {'': {'start'}}  # 到新起始状态的ε转换
    },
    initial_state='start',  # 新起始状态
    final_states={'start', '2'}  # 接受状态包含新起始状态和1.6a的原接受状态
)

自动测试失败输出 #

Running command: $  timeout 15 python3 unit_tests/unit_test_prob_1_10d.py
UNEXPECTED RESULT ON THESE INPUTS: ['0', '1', '00', '01', '11', '000', '001', '010', '011', '101', ...]
Test for: unit_test_prob_1_10d.py
    This test gave you 0 more points
---------------------------------------------------------------------------------------------------------------------------
Running command: $  timeout 15 python3 unit_tests/unit_test_prob_1_10e.py
UNEXPECTED RESULT ON THESE INPUTS: ['1', '01', '10', '11', '001', '010', '011', '100', '101', '110', ...]
Test for: unit_test_prob_1_10e.py
    This test gave you 0 more points

请问我在构造过程中哪里出错了？

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