Computation

Overview

This project provides a suite of Python modules for creating, manipulating, and converting finite automata and regular expressions. The functionalities include operations on Deterministic Finite Automata (DFA), Non-Deterministic Finite Automata (NFA), conversions between them, as well as DFA minimization and regular expression conversion. It also includes examples and test files for demonstration.

Files Overview

• MinimizationTable.py: Implements a table to support DFA minimization, organizing state equivalence checks to reduce redundant states.
• Regex.py: Defines a class for handling regular expressions and includes methods for converting between regex patterns and finite automata.
• dfa.py: Contains the main DFA class that supports operations like state transitions, checking accept states, and constructing DFA structures.
• dfa_to_regex.py: Implements a method for converting DFAs into equivalent regular expressions.
• exceptions.py: Defines custom exception classes for handling errors in automata operations.
• nfa.py: Provides the NFA class, including methods for state transitions, epsilon transitions, and NFA construction.
• test.py: Contains unit tests to validate the functionality of DFA, NFA, and regex operations.

Detailed explaination of Each File

1. MinimizationTable.py

This module contains classes and functions to support DFA minimization:

• Purpose: Reduces DFA states by identifying equivalent states and merging them to create a minimized DFA.
• Main Classes and Methods:
  • MinimizationTable: Constructs a table to check state equivalences based on reachable states and transitions.

2. Regex.py

This module provides functionality for working with regular expressions and converting them into NFAs:

• Purpose: Enables the creation of NFAs from regular expressions and supports the construction of regular expressions from finite automata.
• Main Classes and Methods:
  • Regex: Handles regex parsing and manages the conversion of regex strings into automata structures.
  • to_nfa(): Converts a given regular expression into an NFA.

3. dfa.py

This module defines the DFA class and its associated methods:

• Purpose: Models a DFA with state transition capabilities and validation for accept states.
• Main Classes and Methods:
  • DFA: Represents a deterministic finite automaton, storing states, accept states, and transition functions.
  • is_accept_state(): Checks if the current state is an accept state.
  • transition(): Executes state transitions based on input symbols.

4. dfa_to_regex.py

This file includes logic for converting a DFA into an equivalent regular expression:

• Purpose: Converts the DFA structure into a regex format that matches the same language.
• Main Classes and Methods:
  • dfa_to_regex: Applies an algorithm to translate DFA transitions into a regular expression.

5. exceptions.py

This module defines custom exceptions used across the project to handle specific errors:

• Purpose: Ensures that specific errors related to automata operations are caught and handled gracefully.
• Main Classes and Exceptions:
  • AutomataException: Base exception class for general automata errors.
  • StateError, TransitionError: Specific exceptions for invalid states or transitions.

6. nfa.py

This module contains the NFA class and its functionality:

• Purpose: Models an NFA with support for epsilon transitions and nondeterministic behavior.
• Main Classes and Methods:
  • NFA: Represents a nondeterministic finite automaton with states, transitions, and epsilon transitions.
  • add_epsilon_transition(): Adds epsilon transitions, enabling non-deterministic state transitions.

7. test.py

This module provides unit tests for the various components of the project:

• Purpose: Verifies the accuracy of DFA, NFA, and regex functionalities.
• Main Classes and Methods:
  • test_dfa(), test_nfa(), test_regex(): Test methods that validate the behavior of DFA, NFA, and regex modules under different scenarios.