Create a Python Library for Finite Automata and Regular Languages

# Import necessary libraries
from collections import defaultdict

# Define the State class
class State:
    def __init__(self, name, is_final=False):
        # Initialize state with a name and whether it is a final state
        self.name = name
        self.is_final = is_final

# Define the Transition class
class Transition:
    def __init__(self, from_state, to_state, symbol):
        # Initialize transition with source state, destination state, and transition symbol
        self.from_state = from_state
        self.to_state = to_state
        self.symbol = symbol

# Define the FiniteAutomaton class
class FiniteAutomaton:
    def __init__(self, states, alphabet, transitions, start_state, final_states):
        # Initialize finite automaton with states, alphabet, transitions, start state, and final states
        self.states = {state.name: state for state in states}
        self.alphabet = alphabet
        self.transitions = defaultdict(list)
        for t in transitions:
            self.transitions[t.from_state.name].append((t.symbol, t.to_state.name))
        self.start_state = start_state.name
        self.final_states = {state.name for state in final_states}

    def is_accepting(self, input_string):
        # Determine if the input string is accepted by the automaton
        current_state = self.start_state
        for symbol in input_string:
            if symbol not in self.alphabet:
                return False
            found = False
            for transition_symbol, next_state in self.transitions[current_state]:
                if transition_symbol == symbol:
                    current_state = next_state
                    found = True
                    break
            if not found:
                return False
        return current_state in self.final_states

# Define the DFA class, inheriting from FiniteAutomaton
class DFA(FiniteAutomaton):
    def __init__(self, states, alphabet, transitions, start_state, final_states):
        # Initialize DFA using the FiniteAutomaton initializer
        super().__init__(states, alphabet, transitions, start_state, final_states)

# Define the NFA class, inheriting from FiniteAutomaton
class NFA(FiniteAutomaton):
    def __init__(self, states, alphabet, transitions, start_state, final_states):
        # Initialize NFA using the FiniteAutomaton initializer
        super().__init__(states, alphabet, transitions, start_state, final_states)

    def is_accepting(self, input_string):
        # Determine if the input string is accepted by the NFA using BFS for state exploration
        current_states = {self.start_state}
        for symbol in input_string:
            next_states = set()
            for state in current_states:
                for transition_symbol, next_state in self.transitions[state]:
                    if transition_symbol == symbol:
                        next_states.add(next_state)
            current_states = next_states
            if not current_states:
                return False
        return any(state in self.final_states for state in current_states)

# Example usage
if __name__ == "__main__":
    # Define states for DFA
    s0 = State("S0", is_final=False)
    s1 = State("S1", is_final=True)

    # Define alphabet for DFA
    alphabet = {'0', '1'}

    # Define transitions for DFA (accepts strings ending in '0')
    transitions = [
        Transition(s0, s0, '1'),
        Transition(s0, s1, '0'),
        Transition(s1, s0, '1'),
        Transition(s1, s1, '0')
    ]

    # Create DFA
    dfa = DFA(states=[s0, s1], alphabet=alphabet, transitions=transitions, start_state=s0, final_states=[s1])

    # Test DFA with some input strings
    print(dfa.is_accepting("0"))    # Should be True
    print(dfa.is_accepting("1"))    # Should be False
    print(dfa.is_accepting("10"))   # Should be True
    print(dfa.is_accepting("11"))   # Should be False

    # Define states for NFA
    nfa_s0 = State("S0", is_final=False)
    nfa_s1 = State("S1", is_final=True)

    # Define alphabet for NFA
    nfa_alphabet = {'0', '1'}

    # Define transitions for NFA (accepts strings containing at least one '0')
    nfa_transitions = [
        Transition(nfa_s0, nfa_s0, '1'),
        Transition(nfa_s0, nfa_s1, '0'),
        Transition(nfa_s1, nfa_s1, '0'),
        Transition(nfa_s1, nfa_s1, '1')
    ]

    # Create NFA
    nfa = NFA(states=[nfa_s0, nfa_s1], alphabet=nfa_alphabet, transitions=nfa_transitions, start_state=nfa_s0, final_states=[nfa_s1])

    # Test NFA with some input strings
    print(nfa.is_accepting("0"))    # Should be True
    print(nfa.is_accepting("1"))    # Should be False
    print(nfa.is_accepting("10"))   # Should be True
    print(nfa.is_accepting("11"))   # Should be False