nfa转化为dfa python代码

NFA（非确定性有限自动机）转化为DFA（确定性有限自动机）是通过子集构造法实现的。以下是使用Python代码实现NFA转化为DFA的过程：

class NFA:
    def __init__(self, states, alphabet, transitions, start_state, final_states):
        self.states = states
        self.alphabet = alphabet
        self.transitions = transitions
        self.start_state = start_state
        self.final_states = final_states

    def epsilon_closure(self, states):
        closure = set(states)
        stack = list(states)
        while stack:
            current_state = stack.pop()
            if current_state in self.transitions and 'ε' in self.transitions[current_state]:
                next_states = self.transitions[current_state]['ε']
                new_states = [state for state in next_states if state not in closure]
                closure.update(new_states)
                stack.extend(new_states)
        return closure

    def move(self, states, symbol):
        result = set()
        for state in states:
            if state in self.transitions and symbol in self.transitions[state]:
                result.update(self.transitions[state][symbol])
        return result

    def convert_to_dfa(self):
        dfa_states = []
        dfa_transitions = {}
        start_state = frozenset(self.epsilon_closure([self.start_state]))
        dfa_states.append(start_state)
        stack = [start_state]

        while stack:
            current_state = stack.pop()
            for symbol in self.alphabet:
                next_state = frozenset(self.epsilon_closure(self.move(current_state, symbol)))
                if next_state not in dfa_states:
                    dfa_states.append(next_state)
                    stack.append(next_state)
                if current_state not in dfa_transitions:
                    dfa_transitions[current_state] = {}
                dfa_transitions[current_state][symbol] = next_state

        dfa_final_states = [state for state in dfa_states if any(final_state in state for final_state in self.final_states)]

        return DFA(dfa_states, self.alphabet, dfa_transitions, start_state, dfa_final_states)


class DFA:
    def __init__(self, states, alphabet, transitions, start_state, final_states):
        self.states = states
        self.alphabet = alphabet
        self.transitions = transitions
        self.start_state = start_state
        self.final_states = final_states

    def accept(self, input_string):
        current_state = self.start_state
        for symbol in input_string:
            if symbol in self.transitions[current_state]:
                current_state = self.transitions[current_state][symbol]
            else:
                return False
        return current_state in self.final_states


# 示例用法
nfa = NFA(
    states={'A', 'B', 'C', 'D'},
    alphabet={'0', '1'},
    transitions={
        'A': {'ε': {'B', 'C'}},
        'B': {'0': {'B'}, '1': {'B', 'D'}},
        'C': {'0': {'C', 'D'}, '1': {'C'}},
    },
    start_state='A',
    final_states={'D'}
)

dfa = nfa.convert_to_dfa()

print(dfa.accept('000'))  # 输出 True
print(dfa.accept('111'))  # 输出 False

上述代码实现了NFA转化为DFA的过程。首先定义了NFA类和DFA类，通过epsilon_closure()方法计算ε-closure，move()方法根据给定的symbol计算下一个状态，然后使用子集构造法将NFA转化为DFA，最后通过DFA类的accept()方法来判断给定的输入字符串是否被DFA接受。