program.py

import os

class NFA:
    """
    Represents a Non-deterministic Finite Automaton (NFA).

    :ivar states: Set of states in the NFA.
    :vartype states: set
    :ivar alphabet: Set of symbols in the NFA's alphabet.
    :vartype alphabet: set
    :ivar transitions: Dictionary representing transitions between states.
    :vartype transitions: dict
    :ivar start_state: The start state of the NFA.
    :vartype start_state: str
    :ivar accept_states: Set of accept states in the NFA.
    :vartype accept_states: set
    """

    def __init__(self):
        """
        Initialize an empty NFA.
        """
        self.states = set()  # States in the NFA
        self.alphabet = set()  # Alphabet of the NFA
        self.transitions = {}  # Transitions between states
        self.start_state = None  # Start state
        self.accept_states = set()  # Accept states

    def add_state(self, state, is_start=False, is_accept=False):
        """
        Add a state to the NFA.

        :param state: The name of the state to add.
        :type state: str
        :param is_start: True if the state is the start state, False otherwise.
        :type is_start: bool, optional
        :param is_accept: True if the state is an accept state, False otherwise.
        :type is_accept: bool, optional
        """
        self.states.add(state)  # Add state to set of states
        if is_start:
            self.start_state = state  # Set as start state if is_start is True
        if is_accept:
            self.accept_states.add(state)  # Add to accept states if is_accept is True

    def add_transition(self, from_state, symbol, to_state):
        """
        Add a transition to the NFA.

        :param from_state: The state the transition originates from.
        :type from_state: str
        :param symbol: The input symbol that triggers the transition.
        :type symbol: str
        :param to_state: The state the transition leads to.
        :type to_state: str
        """
        if from_state not in self.transitions:  # Create entry for from_state if not present
            self.transitions[from_state] = {}
        if symbol not in self.transitions[from_state]:  # Create entry for symbol if not present
            self.transitions[from_state][symbol] = set()
        self.transitions[from_state][symbol].add(to_state)  # Add to_state to the transition set
        self.alphabet.add(symbol)  # Add symbol to alphabet

    def epsilon_closure(self, states):
        """
        Compute the epsilon closure of a set of states.

        :param states: The set of states to compute the epsilon closure for.
        :type states: set
        :return: The epsilon closure of the given states.
        :rtype: set
        """
        closure = set(states)  # Initialize closure with given states
        stack = list(states)  # Initialize stack with given states
        while stack:  # While stack is not empty
            state = stack.pop()  # Pop a state from the stack
            if state in self.transitions and '' in self.transitions[state]:  # If epsilon transition exists
                for next_state in self.transitions[state]['']:  # For each epsilon transition
                    if next_state not in closure:  # If next_state not in closure
                        closure.add(next_state)  # Add next_state to closure
                        stack.append(next_state)  # Push next_state to stack
        return closure  # Return the closure

    def move(self, states, symbol):
        """
        Compute the set of states reachable by a given symbol from a set of states.

        :param states: The set of states to start from.
        :type states: set
        :param symbol: The input symbol.
        :type symbol: str
        :return: The set of states reachable by the symbol from the given states.
        :rtype: set
        """
        next_states = set()  # Initialize next_states to empty set
        for state in states:  # Iterate through each state in states
            if state in self.transitions and symbol in self.transitions[state]:  # If transition exists for state and symbol
                next_states.update(self.transitions[state][symbol])  # Update next_states with reachable states
        return next_states  # Return next_states

    def is_accepted(self, input_string):
        """
        Check if the NFA accepts the given input string.

        :param input_string: The input string to test.
        :type input_string: str
        :return: True if the NFA accepts the input string, False otherwise.
        :rtype: bool
        """
        current_states = self.epsilon_closure({self.start_state})  # Start with epsilon closure of start state
        for symbol in input_string:  # Iterate through each symbol in input_string
            if symbol not in self.alphabet:  # If symbol not in alphabet, reject
                return False
            next_states = self.move(current_states, symbol)  # Get next states based on current states and symbol
            current_states = self.epsilon_closure(next_states)  # Update current_states with epsilon closure of next_states
            if not current_states:  # If current_states is empty, reject
                return False
        return any(state in self.accept_states for state in current_states)  # Check if any current state is an accept state

def build_number_nfa():
    """
    Build an NFA that recognizes Python number literals (integers and floats) with underscore support.

    :return: The constructed NFA.
    :rtype: NFA
    """
    nfa = NFA()  # Create a new NFA object

    # Add states to the NFA
    nfa.add_state('start', is_start=True)
    nfa.add_state('sign')
    nfa.add_state('integer', is_accept=True)
    nfa.add_state('zero')
    nfa.add_state('octal_prefix')
    nfa.add_state('octal_digit', is_accept=True)
    nfa.add_state('hex_prefix')
    nfa.add_state('hex_digit', is_accept=True)
    nfa.add_state('decimal_point')
    nfa.add_state('fraction', is_accept=True)
    nfa.add_state('exponent_symbol')
    nfa.add_state('exponent_sign')
    nfa.add_state('exponent', is_accept=True)
    nfa.add_state('underscore')  # New state for underscore

    # Add transitions for sign
    nfa.add_transition('start', '+', 'sign')
    nfa.add_transition('start', '-', 'sign')

    # Add transitions for integer part
    for digit in '123456789':
        nfa.add_transition('start', digit, 'integer')
        nfa.add_transition('sign', digit, 'integer')
        nfa.add_transition('integer', digit, 'integer')
        nfa.add_transition('underscore', digit, 'integer')  # Allow digit after underscore
    nfa.add_transition('start', '0', 'zero')
    nfa.add_transition('sign', '0', 'zero')
    nfa.add_transition('zero', '', 'integer')
    nfa.add_transition('integer', '0', 'integer')
    nfa.add_transition('underscore', '0', 'integer')  # Allow '0' after underscore

    # Add transitions for octal integers
    nfa.add_transition('zero', 'o', 'octal_prefix')
    nfa.add_transition('zero', 'O', 'octal_prefix')
    for digit in '01234567':
        nfa.add_transition('octal_prefix', digit, 'octal_digit')
        nfa.add_transition('octal_digit', digit, 'octal_digit')
        nfa.add_transition('underscore', digit, 'octal_digit')  # Allow octal digit after underscore

    # Add transitions for hexadecimal integers
    nfa.add_transition('zero', 'x', 'hex_prefix')
    nfa.add_transition('zero', 'X', 'hex_prefix')
    for digit in '0123456789abcdefABCDEF':
        nfa.add_transition('hex_prefix', digit, 'hex_digit')
        nfa.add_transition('hex_digit', digit, 'hex_digit')
        nfa.add_transition('underscore', digit, 'hex_digit')  # Allow hex digit after underscore

    # Add transitions for floating-point numbers
    nfa.add_transition('start', '.', 'decimal_point')
    nfa.add_transition('sign', '.', 'decimal_point')
    nfa.add_transition('integer', '.', 'decimal_point')
    nfa.add_transition('zero', '.', 'decimal_point')

    for digit in '0123456789':
        nfa.add_transition('decimal_point', digit, 'fraction')
        nfa.add_transition('fraction', digit, 'fraction')
        nfa.add_transition('underscore', digit, 'fraction')  # Allow digit after underscore in fraction

    for e in 'eE':
        nfa.add_transition('integer', e, 'exponent_symbol')
        nfa.add_transition('zero', e, 'exponent_symbol')
        nfa.add_transition('fraction', e, 'exponent_symbol')

    nfa.add_transition('exponent_symbol', '+', 'exponent_sign')
    nfa.add_transition('exponent_symbol', '-', 'exponent_sign')

    for digit in '0123456789':
        nfa.add_transition('exponent_symbol', digit, 'exponent')
        nfa.add_transition('exponent_sign', digit, 'exponent')
        nfa.add_transition('exponent', digit, 'exponent')
        nfa.add_transition('underscore', digit, 'exponent')  # Allow digit after underscore in exponent

    # Add transitions for underscores
    nfa.add_transition('integer', '_', 'underscore')
    nfa.add_transition('zero', '_', 'underscore')
    nfa.add_transition('octal_digit', '_', 'underscore')
    nfa.add_transition('hex_digit', '_', 'underscore')
    nfa.add_transition('fraction', '_', 'underscore')
    nfa.add_transition('exponent', '_', 'underscore')
    nfa.add_transition('hex_prefix', '_', 'underscore')  # Allow underscore after base prefix
    nfa.add_transition('octal_prefix', '_', 'underscore')  # Allow underscore after base prefix

    return nfa  # Return the constructed NFA

def create_sample_input_files(in_filename, in_ans_filename):
    """
    Create sample input files for testing the NFA.

    :param in_filename: The name of the file to create with just inputs.
    :type in_filename: str
    :param in_ans_filename: The name of the file to create with inputs and expected results.
    :type in_ans_filename: str
    """
    sample_data = [
        "123,a",
        "-456,a",
        "0,a",
        "0x1A,a",
        "0o17,a",
        "3.14,a",
        "-0.5,a",
        "2e10,a",
        "1.5e-5,a",
        ".5,a",
        "1.,a",
        "1a,r",
        "0x,r",
        "0o9,r",
        "+,r",
        "3.14.15,r",
        "1e,r",
        "e5,r"
    ]

    with open(in_filename, 'w') as f_in, open(in_ans_filename, 'w') as f_in_ans:
        for line in sample_data:
            input_string, expected = line.split(',')
            f_in.write(f"{input_string}\n")
            f_in_ans.write(f"{input_string},{expected}\n")

    print(f"Sample input files '{in_filename}' and '{in_ans_filename}' have been created.")

def test_nfa(nfa, in_filename, in_ans_filename, output_filename):
    """
    Test the NFA with input files and write results to an output file.

    :param nfa: The NFA to test.
    :type nfa: NFA
    :param in_filename: The name of the input file containing test cases.
    :type in_filename: str
    :param in_ans_filename: The name of the input file containing test cases with expected results.
    :type in_ans_filename: str
    :param output_filename: The name of the output file to write results to.
    :type output_filename: str
    """
    if not os.path.exists(in_filename) or not os.path.exists(in_ans_filename):
        print(f"Input files '{in_filename}' or '{in_ans_filename}' not found.")
        create = input("Would you like to create sample input files? (y/n): ")
        if create.lower() == 'y':
            create_sample_input_files(in_filename, in_ans_filename)
        else:
            print("File-based testing skipped.")
            return

    with open(in_filename, 'r') as f_in, open(in_ans_filename, 'r') as f_in_ans, open(output_filename, 'w') as f_out:
        for input_line, ans_line in zip(f_in, f_in_ans):
            input_string = input_line.strip()
            ans_input, expected = ans_line.strip().split(',')
            
            if input_string != ans_input:
                print(f"Warning: Mismatch between input files for '{input_string}'")
                continue

            actual = 'a' if nfa.is_accepted(input_string) else 'r'
            result = 'passed' if actual == expected else 'failed'
            
            f_out.write(f"{input_string},{actual},{expected},{result}\n")

    print(f"Testing complete. Results written to '{output_filename}'.")

if __name__ == "__main__":
    nfa = build_number_nfa()

    # Interactive testing
    while True:
        user_input = input("Enter a literal to test (or 'q' to quit): ")
        if user_input.lower() == 'q':
            break
        result = "Valid" if nfa.is_accepted(user_input) else "Invalid"
        print(f"{user_input} is a {result} Python number literal.")

    print("Moving on to file-based testing.")

    # File-based testing
    in_filename = "in.txt"
    in_ans_filename = "in_ans.txt"
    output_filename = "out.txt"

    if not os.path.exists(in_filename) or not os.path.exists(in_ans_filename):
        create = input("Input files not found. Would you like to create sample input files? (y/n): ")
        if create.lower() == 'y':
            create_sample_input_files(in_filename, in_ans_filename)
    
    test_nfa(nfa, in_filename, in_ans_filename, output_filename)