有限自动机

DFA

确定性有限自动机 (DFA) 是一个 5 元组 $(Q,\Sigma ,\delta ,s,F)$,

• $Q$ 是有限集, 称为状态集;
• $\Sigma$ 是有限集, 称为字母表;
• $\delta :Q\times \Sigma \to Q$ 是转移函数;
• $s\in Q$ 是起始状态;
• $F\subseteq Q$ 是接受状态集.

读写头不能改写, 只能右移.

指向原始笔记的链接

正则语言

对 有限自动机 $M$, 若 $A=\{w\in {\Sigma }^{\ast }|M\text{接受}w\}$, 即 $A$ 是 $M$ 的语言, 记为 $L(M)=A$, 也称为 $M$ 识别 $A$.

若存在 DFA 识别语言 $A$, 则称 $A$ 是正则语言.

称两个有限自动机等价, 当且仅当它们语言相同.

正则运算

定义 $A$ 与 $B$ 是两个 语言, 定义正则运算

• 并 $A\cup B=\{x|x\in A\vee x\in B\}$;

• 连接 $A°B=\{xy|x\in A\wedge y\in B\}$;

• 星号 $A^{\ast }=\{x_1{x}_2...x_k|k\ge 0\wedge \forall x_i\in A\}$.

• 正则语言的并是正则语言.

• 正则语言的交是正则语言.

• 正则语言对所有正则运算封闭.

指向原始笔记的链接

指向原始笔记的链接

NFA

非确定型有限自动机 (NFA),

• 每步能以 0 到多种方式进入下一步
• 转移箭头上的符号可以为空串 $\epsilon$, 可以没有输入就转移.

NFA 是一个 5 元组 $(Q,\Sigma ,\delta ,s,F)$,

• $Q$ 是状态集;
• $\Sigma$ 是字母表;
• $\delta :Q\times {\Sigma }_{\epsilon }\to P(Q)$ 是转移函数.
• $s\in Q$ 是起始状态;
• $F\subseteq Q$ 是接受状态集; 其中 ${\Sigma }_{\epsilon }=\Sigma \cup \{\epsilon \}$.

每个 NFA 都有等价的 DFA.

指向原始笔记的链接