Ⅰ 有限状态自动机类型
有限状态自动机是一种理论模型，用于处理输入和产生输出。它主要有两种类型：接收器和转换器。接收器的作用是判断输入是否被接受，而转换器，如Moore机和Mealy机，前者在每个状态下定义输出动作，后者则在每个状态转移中附带输出动作。
区分这两种机器的是它们的确定性：确定有限状态自动机（DFA）对于每个输入仅有一个确定的状态转移，而非确定有限状态自动机（NFA）则允许每个输入有多个可能的转移。NFA由五个元素组成：有限状态集合Q，输入字母表Σ，转移函数δ，初始状态q0和终结状态集合F，它基于当前状态、输入和转移函数决定后续状态。当输入结束后，如果机器停留在F中任一状态，则表示接受该输入，否则拒绝。
尽管NFA在理论上可能显得复杂，但它在实际应用中十分广泛，如数字电路设计、词法分析和文本编辑器程序等。自动机识别的语言L(M)是由机器接受的所有字符串组成的集合，这是衡量其功能和性能的关键指标。
有限状态自动机（FSM "finite state machine" 或者FSA "finite state automaton" ）是为研究有限内存的计算过程和某些语言类而抽象出的一种计算模型。有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。有限状态自动机可以表示为一个有向图。有限状态自动机是自动机理论的研究对象。