class NFA:
    def __init__(self, states, alphabet, transitions, start, accepts):
        self.states = states
        self.alphabet = alphabet
        self.transitions = transitions
        self.start = start
        self.accepts = accepts

def epsilon_closure(nfa, states):
    closure = set(states)
    stack = list(states)
    while stack:
        state = stack.pop()
        if 'epsilon' in nfa.transitions[state]:
            for epsilon_state in nfa.transitions[state]['epsilon']:
                if epsilon_state not in closure:
                    closure.add(epsilon_state)
                    stack.append(epsilon_state)
    return closure

def nfa_to_dfa(nfa):
    dfa_states = []
    dfa_transitions = {}
    dfa_accepts = []

    # Initial state of DFA is the epsilon closure of the NFA's start state
    start_state = epsilon_closure(nfa, [nfa.start])
    dfa_states.append(start_state)

    # Create a stack to perform a breadth-first search
    stack = [start_state]

    while stack:
        current_state = stack.pop()
        for symbol in nfa.alphabet:
            # Get the next state for the given symbol
            next_states = set()
            for state in current_state:
                if symbol in nfa.transitions[state]:
                    next_states.update(nfa.transitions[state][symbol])
            # Compute the epsilon closure of the next state
            next_state_closure = epsilon_closure(nfa, next_states)
            if next_state_closure not in dfa_states:
                dfa_states.append(next_state_closure)
                stack.append(next_state_closure)
            # Update DFA transitions
            dfa_transitions.setdefault(frozenset(current_state), {})[symbol] = next_state_closure

    # Determine DFA's accept states
    for state_set in dfa_states:
        if any(state in nfa.accepts for state in state_set):
            dfa_accepts.append(state_set)

    return DFA(dfa_states, nfa.alphabet, dfa_transitions, start_state, dfa_accepts)

class DFA:
    def __init__(self, states, alphabet, transitions, start, accepts):
        self.states = states
        self.alphabet = alphabet
        self.transitions = transitions
        self.start = start
        self.accepts = accepts

# Example of NFA
nfa = NFA(
    states={'A', 'B', 'C', 'D'},
    alphabet={'0', '1'},
    transitions={
        'A': {'0': ['B', 'C'], 'epsilon': ['C']},
        'B': {'1': ['D']},
        'C': {'0': ['D']},
        'D': {}
    },
    start='A',
    accepts={'D'}
)

# Convert NFA to DFA
dfa = nfa_to_dfa(nfa)
print(dfa.states)
print(dfa.transitions)
print(dfa.accepts)
# ... 上面的代码 ...

# Convert NFA to DFA
dfa = nfa_to_dfa(nfa)

# 打印DFA的状态
print("DFA States:")
for i, state in enumerate(dfa.states):
    print(f"State {i}: {state}")

# 打印DFA的转换表
print("\nDFA Transitions:")
for state, transitions in dfa.transitions.items():
    print(f"State {state}:")
    for symbol, next_state in transitions.items():
        print(f"  On input '{symbol}': Go to state {next_state}")

# 打印DFA的接受状态
print("\nDFA Accept States:")
for state_set in dfa.accepts:
    print(f"State {state_set}")

# 为了可读性，将状态集合转换为字符串
def set_to_string(state_set):
    return ', '.join(str(state) for state in state_set)

# 打印美化后的DFA状态和接受状态
print("\nPretty Print of DFA States and Accept States:")
for i, state_set in enumerate(dfa.states):
    state_str = set_to_string(state_set)
    print(f"State {i}: {state_str}")
    if state_set in dfa.accepts:
        print("  (Accept State)")

# 打印美化后的DFA转换表
print("\nPretty Print of DFA Transitions:")
for state, transitions in dfa.transitions.items():
    state_str = set_to_string(state)
    print(f"State {state_str}:")
    for symbol, next_state in transitions.items():
        next_state_str = set_to_string(next_state)
        print(f"  On input '{symbol}': Go to state {next_state_str}")