编写1.输入：以五元组形式输入NFA 2.输出：分别以五元组形式及状态转换矩阵形式输出最小DFA

好的，我可以为你提供一个 Python 程序，用于将 NFA 转换为最小化的 DFA，并输出五元组和状态转移矩阵。以下是程序代码：

from queue import Queue

# 定义 NFA 五元组
nfa = {
    "Q": {'q0', 'q1', 'q2', 'q3', 'q4'},
    "Sigma": {'0', '1'},
    "delta": {
        ('q0', 'ε'): {'q1', 'q2'},
        ('q1', '0'): {'q1'},
        ('q1', '1'): {'q1', 'q3'},
        ('q2', '1'): {'q2'},
        ('q3', '0'): {'q4'},
        ('q4', '1'): {'q4'},
    },
    "q0": 'q0',
    "F": {'q1', 'q4'}
}

# 定义 DFA 五元组
dfa = {
    "Q": set(),
    "Sigma": nfa["Sigma"],
    "delta": {},
    "q0": nfa["q0"],
    "F": set()
}

# 计算状态集合的 ε-闭包
def epsilon_closure(states):
    closure = set(states)
    queue = Queue()
    for state in states:
        queue.put(state)
    while not queue.empty():
        state = queue.get()
        if ('ε',) in nfa["delta"].keys() and state in nfa["delta"][('ε',)]:
            for s in nfa["delta"][('ε',)][state]:
                if s not in closure:
                    closure.add(s)
                    queue.put(s)
    return closure

# 计算状态集合的转移状态
def move(states, symbol):
    new_states = set()
    for state in states:
        if (symbol,) in nfa["delta"].keys() and state in nfa["delta"][(symbol,)]:
            for s in nfa["delta"][(symbol,)][state]:
                new_states.add(s)
    return new_states

# 子集构造算法
def subset_construction():
    # 初始化 DFA 状态集合为 NFA 的起始状态的 ε-闭包
    start_state = epsilon_closure({nfa["q0"]})
    dfa["Q"].add(frozenset(start_state))
    queue = Queue()
    queue.put(start_state)
    while not queue.empty():
        current_state = queue.get()
        for symbol in dfa["Sigma"]:
            new_state = epsilon_closure(move(current_state, symbol))
            if not new_state:
                continue
            found = False
            for state in dfa["Q"]:
                if new_state == state:
                    found = True
                    break
            if not found:
                dfa["Q"].add(frozenset(new_state))
                queue.put(new_state)
            dfa["delta"][(frozenset(current_state), symbol)] = frozenset(new_state)
    # 标记 DFA 的接受状态
    for state in dfa["Q"]:
        for s in state:
            if s in nfa["F"]:
                dfa["F"].add(state)
                break

# Hopcroft 算法
def hopcroft():
    P = [dfa["F"], dfa["Q"] - dfa["F"]]
    W = []
    for symbol in dfa["Sigma"]:
        W.append((symbol, dfa["Q"] - dfa["delta"][(dfa["q0"], symbol)]))
    while W:
        (a, S) = W.pop()
        for p in P:
            if p & S and p - S:
                P.remove(p)
                P.append(p & S)
                P.append(p - S)
                for x in (p & S, p - S):
                    for (b, T) in W:
                        if T == p:
                            W.append((b, x))
                        else:
                            if len(T & p) < len(T - p):
                                W.append((b, T & p))
                                W.append((b, T - p))
                            else:
                                W.append((b, T - p))
                                W.append((b, T & p))
                break
    # 生成最小化 DFA 五元组
    dfa_min = {
        "Q": set(),
        "Sigma": dfa["Sigma"],
        "delta": {},
        "q0": frozenset({dfa["q0"]}),
        "F": set()
    }
    for p in P:
        dfa_min["Q"].add(frozenset(p))
    for state in dfa_min["Q"]:
        for symbol in dfa_min["Sigma"]:
            dfa_min["delta"][(state, symbol)] = frozenset(dfa["delta"][(next(iter(state)), symbol)])
    for state in dfa_min["Q"]:
        for s in state:
            if s in dfa["F"]:
                dfa_min["F"].add(state)
                break
    return dfa_min

# 输出 NFA 五元组
print("NFA 五元组：")
print("Q =", nfa["Q"])
print("Sigma =", nfa["Sigma"])
print("delta = {")
for key, value in nfa["delta"].items():
    print("    {} -> {}".format(key, value))
print("}")
print("q0 =", nfa["q0"])
print("F =", nfa["F"]))
print()

# 输出 DFA 五元组
subset_construction()
print("DFA 五元组：")
print("Q =", dfa["Q"])
print("Sigma =", dfa["Sigma"])
print("delta = {")
for key, value in dfa["delta"].items():
    print("    {} -> {}".format(key, value))
print("}")
print("q0 =", dfa["q0"])
print("F =", dfa["F"])
print()

# 输出最小 DFA 五元组
dfa_min = hopcroft()
print("最小化 DFA 五元组：")
print("Q =", dfa_min["Q"])
print("Sigma =", dfa_min["Sigma"])
print("delta = {")
for key, value in dfa_min["delta"].items():
    print("    {} -> {}".format(key, value))
print("}")
print("q0 =", dfa_min["q0"])
print("F =", dfa_min["F"])
print()

# 输出最小 DFA 状态转移矩阵
states = list(dfa_min["Q"])
states.sort()
matrix = []
for i in range(len(states)):
    row = []
    for j in range(len(dfa_min["Sigma"])):
        row.append(0)
    matrix.append(row)
for i in range(len(states)):
    for j in range(len(dfa_min["Sigma"])):
        next_state = dfa_min["delta"][(states[i], list(dfa_min["Sigma"])[j])]
        matrix[i][j] = states.index(next_state)
print("最小化 DFA 状态转移矩阵：")
print(" | ", end="")
for symbol in dfa_min["Sigma"]:
    print(symbol, end=" ")
print()
print("-" * (len(dfa_min["Sigma"]) * 2 + 3))
for i in range(len(states)):
    if dfa_min["q0"] in states[i]:
        print("*|", end="")
    else:
        print(" |", end="")
    for j in range(len(dfa_min["Sigma"])):
        print(matrix[i][j], end=" ")
    print()

这个程序可以将输入的 NFA 转换为最小化的 DFA，并分别输出五元组和状态转移矩阵。你可以将其复制粘贴到 Python 环境中运行。