FSM

13. Finite State Machines -Deterministic Finite State Automata DFSA
14. Finite-State machine conversion from NDFSA tO DFSA
15. Finite-state machine limitations
16. Push Down Automata and Context Free Grammars and their limitations

FSM

DFSA

核心概念	考点讲解	示例
形式定义	$A=(Q, \Sigma, \delta, q_0, F)$	Q: 状态集；$\Sigma$: 输入字母表；$q_0$: 初始状态；$F$: 接受状态集。
关键特性	转移函数：$\delta: Q \times \Sigma \rightarrow Q$。确定性指对任一状态 $q$ 和输入符号 $a$，下一个状态 $\delta(q, a)$ 都是唯一确定的。	识别语言 $L=\{w \mid w \text{ 包含偶数个 } 0\}$。只需要两个状态 $q_0$ (偶数个0) 和 $q_1$ (奇数个0)。
语言识别	$L(A) = \{w \in \Sigma^* \mid \delta_w(q_0, w) \in F\}$。一个字 $w$ 被接受，当且仅当自动机从 $q_0$ 读完 $w$ 后停在一个接受状态中。

NDFSA

核心概念	形式定义/解释	来源
转移函数	$\delta: Q \times \Sigma \rightarrow 2^Q$ 33333333。	给定当前状态和输入符号，输出是一个状态集合（$Q$ 的幂集）而非单个状态，因此存在多条计算路径 34343434。
接受条件	如果存在至少一条计算路径以最终状态 $q \in F$ 结束，则 NDFSA 接受该字 $w$ 35353535。	与 DFSA 相比，NDFSA 允许存在多条路径 36。
等价性	NDFSA 和 DFSA 的集合是等价的 37。	对于任何 NDFSA $A$，都可以构造一个等价的 DFSA $B$ 使得 $L(A) = L(B)$ 38。转换方法：DFSA 的每个状态代表 NDFSA 状态的一个子集（即 $Q' = 2^Q$） 39393939。

NDFSA -> DFSA

核心概念	考点讲解	示例/方法
等价性	NDFSA 和 DFSA 具有相同的识别能力，它们都只能识别正则语言 (Regular Languages)。	转换的目的是为了便于计算机实现，因为 DFSA 的行为是确定的。
转换方法	子集构造法 (Subset Construction)
步骤	1. 新状态集 $Q'$：DFSA 的每个状态对应 NDFSA 状态的一个子集（$Q'$ 是 $Q$ 的幂集 $2^Q$ 的子集）。2. 初始状态 $q'_0$：是 NDFSA 初始状态 $q_0$ 构成的集合。3. 新转移函数 $\delta'$：对于 DFSA 的状态 $S \subseteq Q$ 和输入 $a$，$\delta'(S, a)$ 定义为所有 NDFSA 状态 $q \in S$ 经过 $a$ 转移到的所有状态的集合：$\delta'(S, a) = \bigcup_{q \in S} \delta(q, a)$。4. 接受状态 $F'$：$F'$ 中的状态 $S$ 必须包含至少一个 NDFSA 的接受状态 $f \in F$。

FSM limitation

局限性	考点讲解	经典反例
无法计数	DFSA/NDFSA 只有有限个状态，这限制了其记忆能力。它无法记住任意长度、数量不确定的信息。	$L=\{a^n b^n \mid n \ge 1\}$。自动机无法记住 $a$ 的任意数量 $n$，以便稍后匹配相同数量的 $b$。
无法识别	FSM 只能识别正则语言。对于需要堆栈或更复杂内存结构才能识别的上下文无关语言 (CFL)，FSM 无能为力。	$L=\{w w^R \mid w \in \{0, 1\}^*\}$ (回文串语言)。FSM 无法记住前半段 $w$ 以便反向匹配 $w^R$。

PDA

核心概念	考点讲解	示例
CFG	$G=(V, T, P, S)$。用于描述上下文无关语言 (CFL)。是比正则语言更强大的语言类别。	$S \rightarrow aSb \mid \epsilon$。生成 $L=\{a^n b^n \mid n \ge 0\}$。
PDA 结构	FSM + 栈 (Stack)。栈提供了一个无限的 LIFO (后进先出) 内存，用于存储和检索信息。
PDA 转移函数	$\delta: Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma \rightarrow \text{有限集合 of } (Q \times \Gamma^*)$。它不仅依赖于输入符号和当前状态，还依赖于栈顶符号。	识别 $L=\{a^n b^n\}$：当读取 $a$ 时，将 $A$ 压入栈（计数）；当读取 $b$ 时，弹出一个 $A$（匹配）。
PDA 局限性	PDA 只能识别上下文无关语言 (CFL)。它无法处理需要随机存取或非 LIFO 内存的语言。	$L=\{a^n b^n c^n \mid n \ge 1\}$。PDA 无法同时匹配三种字母的数量关系。需要更强大的模型——图灵机来识别。