nfa和dfa的代码

NFA（Non-Deterministic Finite Automaton，非确定有限自动机）和DFA（Deterministic Finite Automaton，确定有限自动机）是计算机科学中的两种自动机模型。它们描述了一种抽象的计算模型，用于解决字符串匹配、模式识别等问题。

NFA使用状态转移图的形式描述，一个状态可以有多个后继状态，且可以根据输入字符选择多个转移路径。NFA的代码实现可以使用状态转移表或状态转移函数来表示。以下是一个简单的NFA代码示例：

class NFA:
    def __init__(self, states, alphabet, transitions, start_state, accept_states):
        self.states = states  # 所有状态的集合
        self.alphabet = alphabet  # 输入字符集合
        self.transitions = transitions  # 状态转移函数
        self.start_state = start_state  # 初始状态
        self.accept_states = accept_states  # 接受状态集合

    def accept_input(self, input_string):
        current_states = set([self.start_state])  # 当前状态集合
        for char in input_string:
            next_states = set()
            for state in current_states:
                if (state, char) in self.transitions:  # 根据输入字符和当前状态找到后继状态
                    next_states.update(self.transitions[(state, char)])
            current_states = next_states
        return bool(current_states & self.accept_states)  # 判断是否有接受状态

# 使用示例
states = {0, 1, 2}  # 状态集合
alphabet = {'a', 'b'}  # 输入字符集合
transitions = {(0, 'a'): {1}, (1, 'b'): {2}}  # 状态转移函数
start_state = 0  # 初始状态
accept_states = {2}  # 接受状态集合

nfa = NFA(states, alphabet, transitions, start_state, accept_states)
result = nfa.accept_input('ab')
print(result)  # 输出：True

DFA是一种特殊的NFA，不同于NFA的是，DFA的任意状态只有一个后继状态，并且不允许有空转移。DFA可使用状态转移表或状态转移函数实现。以下是一个简单的DFA代码示例：

class DFA:
    def __init__(self, states, alphabet, transitions, start_state, accept_states):
        self.states = states  # 所有状态的集合
        self.alphabet = alphabet  # 输入字符集合
        self.transitions = transitions  # 状态转移函数
        self.start_state = start_state  # 初始状态
        self.accept_states = accept_states  # 接受状态集合

    def accept_input(self, input_string):
        current_state = self.start_state  # 当前状态
        for char in input_string:
            current_state = self.transitions[(current_state, char)]  # 根据输入字符和当前状态找到后继状态
        return current_state in self.accept_states  # 判断是否为接受状态

# 使用示例
states = {0, 1, 2}  # 状态集合
alphabet = {'a', 'b'}  # 输入字符集合
transitions = {(0, 'a'): 1, (0, 'b'): 0, (1, 'a'): 1, (1, 'b'): 2, (2, 'a'): 1, (2, 'b'): 0}  # 状态转移函数
start_state = 0  # 初始状态
accept_states = {2}  # 接受状态集合

dfa = DFA(states, alphabet, transitions, start_state, accept_states)
result = dfa.accept_input('ab')
print(result)  # 输出：True