计算机科学理论 - 状态图 NFA

Question

-1.6a

使用定理 1.49 证明中的构造给出识别所描述语言之星的 NFA 的状态图。为 1.6a 和 1.6k 制作一个

-1.6a

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'}
)

-1.6k

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'}
)

对于 1.6a，这就是我所做的：

prob_1_10d = NFA(
    states={'0', '1', '2', '3', 'start'},  # Add a new start state
    input_symbols={'0', '1'},
    transitions={
        'start': {'': {'0'}},  # Epsilon transition from new start state to old start state
        '0': {'0': {'3'}, '1': {'1'}, '': {'start'}},  # Add epsilon transition back to start state for Kleene star
        '1': {'1': {'1'}, '0': {'2'}, '': {'start'}},  # Add epsilon transition back to start state for Kleene star
        '2': {'0': {'2'}, '1': {'1'}, '': {'start'}},  # Add epsilon transition back to start state for Kleene star
        '3': {'': {'start'}}  # Epsilon transition back to start state for Kleene star
    },
    initial_state='start',  # New initial state with an epsilon transition
    final_states={'start'}  # Only the new start state is the final state
)

对于 1.6k，这就是我所做的：

prob_1_10e = NFA(
    states={'0', '1', '2', '3', 'start'},  # The original states plus a new start state for the Kleene star
    input_symbols={'0', '1'},
    transitions={
        'start': {'': {'0', 'start'}},  # Epsilon transitions to the original start state and itself
        '0': {'0': {'3'}, '1': {'1'}, '': {'start'}},  # Epsilon transition to the new start state
        '1': {'0': {'2'}, '1': {'1'}, '': {'start'}},  # Epsilon transition to the new start state
        '2': {'0': {'2'}, '1': {'1'}, '': {'start'}},  # Epsilon transition to the new start state
        '3': {'': {'start'}}  # Epsilon transition to the new start state
    },
    initial_state='start',  # The new start state
    final_states={'start', '2'}  # Final states include the new start state and the original final state from 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

Answer 1

您应该只添加从最终状态回到开始状态的 epsilon 转换。

您似乎从每个状态都转换回开始状态。