Theory of Comp Sci - State Diagrams NFAs

Question

1.49 Theorem

Here is a correct example:

As here is an example for one that is correct:

prob_1_10c = NFA(
    states={"q0", "q1", "q2"},
    input_symbols={"0", "1"},
    transitions={
        "q0": {"": {"q1"}, "0": {}, "1": {}},
        "q1": {"": {"q0", "q1"}, "0": {"q2"}, "1": {"q2"}},
        "q2": {"": {}, "0": {"q2"}, "1": {"q2"}},
    },
    initial_state="q0",
    final_states={"q0", "q1"},
)

Which is based from this:

prob_1_6m = DFA(
    states={'q0'},
    input_symbols={'0', '1'},
    transitions={
        'q0': {'0': 'q0', '1': 'q0'}
    },
    initial_state='q0',
    final_states=set()
)

Use the construction in the proof of Theorem 1.49 to give the state diagrams of NFAs recognizing the star of the languages described. Make one for 1.6a and 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'}
)

for 1.6a this is what I did:

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
)

for 1.6k this is what I did:

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
)

Autograder output:

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

You should only add an epsilon transition from final states back to the start state.

You seem to have transitions from every state back to the start state.