python正规文法转有穷自动机代码

将正则表达式转换为NFA的算法是Thompson算法，然后将NFA转换为DFA的算法是子集构造算法。下面是Python代码实现：

class State:
    def __init__(self):
        self.transitions = {}

    def add_transition(self, symbol, state):
        if symbol in self.transitions:
            self.transitions[symbol].append(state)
        else:
            self.transitions[symbol] = [state]

class NFA:
    def __init__(self, start, accept):
        self.start = start
        self.accept = accept

    def match(self, string):
        current_states = [self.start]
        for symbol in string:
            next_states = []
            for state in current_states:
                if symbol in state.transitions:
                    next_states.extend(state.transitions[symbol])
            current_states = next_states

        return self.accept in current_states

def regex_to_nfa(regex):
    stack = []
    for symbol in regex:
        if symbol == '|':
            right = stack.pop()
            left = stack.pop()
            start = State()
            accept = State()
            start.add_transition('eps', left.start)
            start.add_transition('eps', right.start)
            left.accept.add_transition('eps', accept)
            right.accept.add_transition('eps', accept)
            stack.append(NFA(start, accept))
        elif symbol == '.':
            right = stack.pop()
            left = stack.pop()
            left.accept.add_transition('eps', right.start)
            stack.append(NFA(left.start, right.accept))
        elif symbol == '*':
            nfa = stack.pop()
            start = State()
            accept = State()
            start.add_transition('eps', nfa.start)
            start.add_transition('eps', accept)
            nfa.accept.add_transition('eps', nfa.start)
            nfa.accept.add_transition('eps', accept)
            stack.append(NFA(start, accept))
        else:
            start = State()
            accept = State()
            start.add_transition(symbol, accept)
            stack.append(NFA(start, accept))

    return stack.pop()

def nfa_to_dfa(nfa):
    def epsilon_closure(states):
        closure = set(states)
        queue = list(states)
        while queue:
            state = queue.pop(0)
            if 'eps' in state.transitions:
                for next_state in state.transitions['eps']:
                    if next_state not in closure:
                        closure.add(next_state)
                        queue.append(next_state)

        return closure

    alphabet = set()
    for state in nfa.start.transitions:
        if state != 'eps':
            alphabet.add(state)

    dfa_start = frozenset(epsilon_closure([nfa.start]))
    dfa_states = {dfa_start}
    dfa_transitions = {}
    dfa_accept = set()
    queue = [dfa_start]
    while queue:
        current_state = queue.pop(0)
        for symbol in alphabet:
            next_states = set()
            for state in current_state:
                if symbol in state.transitions:
                    next_states.update(state.transitions[symbol])
            next_states = epsilon_closure(next_states)
            if not next_states:
                continue

            if next_states not in dfa_states:
                dfa_states.add(next_states)
                queue.append(next_states)

            dfa_transitions[(current_state, symbol)] = next_states

        if nfa.accept in current_state:
            dfa_accept.add(current_state)

    return (dfa_states, alphabet, dfa_transitions, dfa_start, dfa_accept)

regex = input("Enter a regular expression: ")
nfa = regex_to_nfa(regex)
dfa_states, alphabet, dfa_transitions, dfa_start, dfa_accept = nfa_to_dfa(nfa)

print("States:", dfa_states)
print("Alphabet:", alphabet)
print("Transitions:", dfa_transitions)
print("Start state:", dfa_start)
print("Accept states:", dfa_accept)

这段代码可以将正则表达式转换为DFA，并打印出DFA的状态集合、字母表、转移函数、起始状态和接受状态。