正则语言

对 有限自动机 $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\}$.

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

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

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

指向原始笔记的链接