NFA转DFA用代码实现时输入输出

以下是 Python 代码实现 NFA 转 DFA 的过程，包含输入输出：

def epsilon_closure(states, transitions):
    """
    计算状态集合 states 的 epsilon 闭包
    """
    closure = set(states)
    stack = list(states)
    while stack:
        state = stack.pop()
        if state in transitions and '' in transitions[state]:
            for s in transitions[state]['']:
                if s not in closure:
                    closure.add(s)
                    stack.append(s)
    return closure

def move(states, transitions, symbol):
    """
    计算状态集合 states 在符号 symbol 下的转移状态
    """
    move_states = set()
    for state in states:
        if state in transitions and symbol in transitions[state]:
            move_states.update(transitions[state][symbol])
    return move_states

def nfa_to_dfa(nfa_states, nfa_transitions, start_state):
    """
    将 NFA 转换为 DFA
    """
    dfa_states = []
    dfa_transitions = {}
    dfa_start_state = frozenset(epsilon_closure([start_state], nfa_transitions))
    unmarked_states = [dfa_start_state]

    while unmarked_states:
        dfa_state = unmarked_states.pop()
        if dfa_state not in dfa_states:
            dfa_states.append(dfa_state)

        for symbol in nfa_alphabet:
            move_states = move(dfa_state, nfa_transitions, symbol)
            closure = epsilon_closure(move_states, nfa_transitions)
            if closure:
                dfa_transitions[(dfa_state, symbol)] = frozenset(closure)
                if closure not in dfa_states + unmarked_states:
                    unmarked_states.append(closure)
    
    return dfa_states, dfa_transitions, dfa_start_state

# 输入示例
nfa_states = {'q0', 'q1', 'q2', 'q3'}
nfa_alphabet = {'0', '1'}
nfa_transitions = {
    'q0': {'': {'q1', 'q2'}},
    'q1': {'0': {'q1'}, '1': {'q1', 'q3'}},
    'q2': {'0': {'q2', 'q3'}, '1': {'q2'}},
    'q3': {'1': {'q3'}}
}
start_state = 'q0'

# 输出示例
dfa_states, dfa_transitions, dfa_start_state = nfa_to_dfa(nfa_states, nfa_transitions, start_state)
print('DFA States:', dfa_states)
print('DFA Transitions:', dfa_transitions)
print('DFA Start State:', dfa_start_state)

在上述代码中，我们首先定义了输入的 NFA 状态集合 `nfa_states`、字母表 `nfa_alphabet`、转移函数 `nfa_transitions` 和起始状态 `start_state`。接着调用 `nfa_to_dfa()` 函数将 NFA 转换为 DFA，并输出转换后的 DFA 状态集合、转移函数和起始状态。