Theory of computer science problems

I am working on theory of computer science problems but cannot get these to work:

a. Give an NFA recognizing the language (01 ∪ 001 ∪ 010)^*

b. Convert this NFA to an equivalent DFA. Give only the portion of the DFA that is reachable from the start state.

I am using the automata.fa package to encode the automata and have them tested. Here are examples:

# example DFA syntax
example_dfa = DFA(
    states={'q1', 'q2', 'q3', 'q4', 'q5'},
    input_symbols={'0', '1'},
    transitions={
        'q1': {'0': 'q1', '1': 'q2'},
        'q2': {'0': 'q1', '1': 'q3'},
        'q3': {'0': 'q2', '1': 'q4'},
        'q4': {'0': 'q3', '1': 'q5'},
        'q5': {'0': 'q4', '1': 'q5'}
    },
    initial_state='q3',
    final_states={'q3'}
)

# example NFA syntax
example_nfa = NFA(
    states={"q0", "q1", "q2"},
    input_symbols={"0", "1"},
    transitions={
        "q0": {"": {"q1", "q2"}},
        "q1": {"0": {"q1"}, "1": {"q2"}},
        "q2": {"0": {"q1"}, "1": {"q2"}},
    },
    initial_state="q0",
    final_states={"q1"},
)

# example regular expression syntax
example_regex = "(a*ba*(a|b)*)|()"

For the above question, I tried with the following diagram for the NFA:

from automata.fa.nfa import NFA

prob_1_17a = NFA(
    states={'q0', 'q1', 'q2', 'q3'},
    input_symbols={'0', '1'},
    transitions={
        'q0': {'0': {'q3'}, '1': {'q0'}},
        'q1': {'0': {'q1'}, '1': {'q0'}},
        'q2': {'0': {'q0'}, '1': {'q2'}},
        'q3': {'0': {'q1'}, '1': {'q2'}},
    },
    initial_state='q0',
    final_states={'q0'}
)

but the autograder gives the following output:

Results:

Running command:

$ timeout 15 python3 unit_tests/unit_test_prob_1_17a.py

UNEXPECTED RESULT ON THESE INPUTS:

['01', '00101', '01001', '01010', '010101', '00100101', '00101001', '00101010', '01000101', '01001001', ...]

Test for: unit_test_prob_1_17a.py

This test gave you 0 more points

How to design the correct NFA/DFA?

Your attempt to an NFA can be visualised like this:

This is not correct. For instance, it allows input to start with a 1, which the language does not allow. The loop at q₂ would allow an input to have consecutive 1s, but that is never possible. The loop at q₁ would allow the input to have any sequence of 0s, but the language can never accept a string that has four or more consecutive 0s.

On the other hand your attempt does not accept the valid input "01", because the state will be at q₂ after such input, and that is not an accept state in your NFA.

How to design the NFA

To design an NFA for the language (01 ∪ 001 ∪ 010)^* we could take it step by step. First design a diagram for the language (01)^*:

q₀ is the start and accept state, and q₄ is the sink for invalid input. Then extend it to (01 ∪ 001)^*:

And then complete to (01 ∪ 001 ∪ 010)^*:

How to design the DFA from the NFA

To design a corresponding DFA, define a state for each possible set of states in the NFA. So for instance (𝑞₁,𝑞₂) is one such state, and (𝑞₀,𝑞₁,𝑞₂) is another. There are many of such states, but only some are really reachable.

Using powerset construction we can identify which input prefixes lead to which states in the NFA, and we can assign to each unique state combination a distinct DFA state. As soon as we find a same combination of NFA states that we already encountered with another prefix, we don't need to lengthen that prefix more, and so we get this table of possibilities:

I chose names for the states of the DFA that reflect how they map to a set of states in the NFA. Each DFA state that corresponds to an NFA state combination that includes 𝑞₀ is accepting.

This leads to the following DFA:

Python code

The above NFA and DFA can be represented as follows:

nfa = NFA(
    states={'q0', 'q1', 'q2', 'q3', 'q4'},
    input_symbols={'0', '1'},
    transitions={
        'q0': {'0': {'q1','q2'}, '1': {'q4'}},
        'q1': {'0': {'q4'},      '1': {'q0'}},
        'q2': {'0': {'q1'},      '1': {'q3'}},
        'q3': {'0': {'q0'},      '1': {'q4'}},
        'q4': {'0': {'q4'},      '1': {'q4'}} # Sink
    },
    initial_state='q0',
    final_states={'q0'}
)

dfa = DFA(
    states={'q0', 'q1', 'q12', 'q03', 'q012', 'q4'},
    input_symbols={'0', '1'},
    transitions={
        'q0'  : {'0': 'q12',  '1': 'q4' },
        'q12' : {'0': 'q1',   '1': 'q03'},
        'q1'  : {'0': 'q4',   '1': 'q0' },
        'q03' : {'0': 'q012', '1': 'q4' },
        'q012': {'0': 'q12',  '1': 'q03'},
        'q4':   {'0': 'q4',   '1': 'q4' } # Sink
    },
    initial_state='q0',
    final_states={'q0', 'q03', 'q012'}
)