Create a Python Library for Finite Automata and Regular Languages

Write a Python program to create a library for working with finite automata and regular languages.

Develop a Python library to facilitate operations with finite automata and regular languages. This library should support creating and manipulating both deterministic (DFA) and non-deterministic finite automata (NFA), allowing for the definition of states, transitions, and acceptance conditions. Additionally, it should provide methods for evaluating strings against these automata to determine acceptance, enabling practical applications in pattern recognition and language processing.

Sample Solution:

Python Code :

# 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

Output:

(base) C:\Users\ME>python untitled1.py
True
False
True
False
True
False
True
False

Explanation:

• State Class: Defines a state with a name and an optional flag for being a final state.
• Transition Class: Represents a transition between states with a given symbol.
• FiniteAutomaton Class: A base class for finite automata with states, alphabet, transitions, a start state, and final states.
• DFA Class: Inherits from "FiniteAutomaton" and represents a deterministic finite automaton.
• NFA Class: Inherits from "FiniteAutomaton" and represents a non-deterministic finite automaton, using BFS for state exploration.
• Example Usage: Demonstrates creating a DFA that accepts strings ending in '0' and an NFA that accepts strings containing at least one '0'.

Python Code Editor :

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: Track and Analyze Software Metrics with Python.