编写程序实现dfa功能

编写程序实现有限状态自动机（Deterministic Finite Automaton，DFA）通常涉及以下几个步骤：

1. 定义状态集：首先，你需要确定机器的所有可能状态。这可以是一个整数数组或者类的对象。

2. 定义输入字母集：确定机器能够识别的字符或符号集。

3. 状态转移函数：为每个状态和每个输入定义一个映射，描述从当前状态到下一个状态的过程。例如，你可以创建一个二维数组，其中索引表示状态，值表示接收到特定输入后的下标。

4. 初始状态：指定机器开始时所在的初始状态。

5. 终止状态：标记那些接收特定输入序列后会进入的状态，它们被视为接受状态。

6. 实现机器：你可以选择用循环结构模拟状态转移过程，每次读取输入并更新状态，直到达到终止状态或者遍历完所有输入。

7. 提供接口：为了使用这个DFA，需要设计一个公共接口，比如函数`isAccepted(input: str) -> bool`，它接受一个字符串作为输入，并返回该串是否能被DFA接受。

下面是一个简单的Python示例（使用字典来表示状态转移矩阵）：

class DFA:
    def __init__(self, states, input_alphabet, initial_state, final_states):
        self.states = states
        self.input_alphabet = input_alphabet
        self.start = initial_state
        self.accepting_states = set(final_states)

    def isAccepted(self, input_string):
        current_state = self.start
        for char in input_string:
            if char not in self.input_alphabet:
                return False
            current_state = self.states[current_state][char]
            if current_state in self.accepting_states:
                return True
        return current_state in self.accepting_states

# 使用示例
d = DFA(states={0: {0, 1}, 1: {1}}, 
       input_alphabet={'a', 'b'}, 
       initial_state=0, 
       final_states={1})
print(d.isAccepted('ab'))  # 输出：True，因为'a'和'b'分别将状态从0转到1，然后从1转到1，最终在1处接受