main.py

import json

# READ DFA FROM DFA.JSON FILE
with open("DFA.json", "r") as file:
    data = json.load(file)
    states = data["states"]
    input_symbols = data["input_symbols"]
    start_state = data["start_state"]
    final_states = data["final_states"]

# Function to display the DFA
def display_dfa():
    print("Display original DFA:")
    print("      ", "  ".join(input_symbols))
    print("-----------------------------------")
    for state, transitions in states.items():
        print(f"{str(state):<6}", "  ".join([transitions[symbol] for symbol in input_symbols]))

# Function to minimize the DFA
def minimize_dfa(states, final_states, input_symbols):
    # Function to check if the next states of two given states are in the same group in the partition
    # For example            Groups: {[A,B,C], [D]}
    # RETURN TRUE           RETURN FALSE
    #        0   1           0   1
    #   s1   B   C           A   B
    #   s2   B   C           A   D
    def check(s1, s2, partition):
        # For each state (s1, s2), take the next states for each input symbol
        # and compare which group the next states are in
        # If the next states are not in the same group, it means the states are not indistinguishable
        for symbol in input_symbols:
            next_state_s1 = states[s1][symbol]  # Next state for s1
            next_state_s2 = states[s2][symbol]  # Next state for s2

            # Find the groups in which the next states appear
            group1 = next((group for group in partition if next_state_s1 in group), None)
            group2 = next((group for group in partition if next_state_s2 in group), None)
    
            if group1 != group2:  # If the next states are not in the same group
                return False
            
        return True

    # First, partition the DFA into two partitions: final states and non-final states
    non_final_states = {state for state in states if state not in final_states}
    # Create an initial partition with final and non-final states
    # one partition for final states and one for non-final states
    partition = [list(non_final_states), list(final_states)] 

    # Step 2: Split states based on equivalence
    changed = True          # Flag to check if the partition has changed
    while changed:          
        changed = False     # Reset the flag
        new_partition = []  # New partition

        # Check each group in the partition
        # Initially, the group will contain all states, then we will split them into subgroups based on the result of the check function
        for group in partition:            
            if len(group) <= 1: # If the group has only one state, we cannot split further
                new_partition.append(group) # Add the group to the new partition
                continue

            subgroups = []  # List for created groups
            visited = []    # List for already visited states

            # Check each state in the group
            for state in group:
                if state not in visited:    
                    # Create a subgroup for the current state
                    current_subgroup = {state}  # Set to avoid duplicate states
                    for other_state in group:   # Check each state in the group
                        if other_state != state and check(state, other_state, partition):  # Check if the states are indistinguishable
                            current_subgroup.add(other_state)   # Add the state to the subgroup
                            visited.append(other_state)         # Mark the state as visited
                    subgroups.append(list(current_subgroup))  # Convert to list and add the subgroup to the list of subgroups
                
            new_partition.extend(subgroups) # Add the subgroups to the new partition
        
        # If the partitioning has changed, set the "changed" flag for a new iteration and start over
        # for the newly created groups
        if len(new_partition) != len(partition):
            changed = True

        partition = new_partition

    minimized_states = {}   # Dictionary for minimized states
    state_mapping = {}      # Dictionary to map old states to new states

    # Iterate through each group in the partition and choose a representative state
    for group in partition:
        representative = group[0]  # The first state in the group becomes the representative of that group
        minimized_states[representative] = {}  # Add the representative to the minimized states dictionary, with an empty dictionary for transitions
        
        # Map each state in the group to the representative of the group
        for state in group:
            state_mapping[state] = representative  

    # Build transitions for minimized states using mapped states
    for group in partition:
        representative = group[0]  # Choose the representative of the current group
        for symbol in input_symbols:  # Iterate through each input symbol
            dest = states[representative][symbol]  # Get the next state for the current symbol
            minimized_states[representative][symbol] = state_mapping[dest]  # Add the corresponding transition to the new minimized state

    # Determine the minimized start state and minimized final states based on mapped states
    minimized_start_state = state_mapping[start_state]  # Determine the minimized start state
    minimized_final_states = {state_mapping[state] for state in final_states}   # Determine the minimized final states

    # Return minimized states, minimized start state, minimized final states, and final partition
    return minimized_states, minimized_start_state, minimized_final_states, partition

# Display original DFA
display_dfa()

# Minimize the DFA
minimized_states, minimized_start_state, minimized_final_states, partition = minimize_dfa(states, final_states, input_symbols)

# Display minimized DFA
print("\nMinimized DFA:")
print("Minimized DFA states:", [group for group in partition])

print("Renaming minimized DFA states:")
keys = list(minimized_states.keys())
for group in partition:
    print(f"{str(group):<15} ->  {keys[partition.index(group)]}")

print(f"\nMinimized start state: {minimized_start_state}")
print(f"Minimized final states: {minimized_final_states}")

print("\nMinimized DFA transitions:")
for state, transitions in minimized_states.items():
    print(f"{state} -> {transitions}")