一、正则语言引入

---

1 . 非确定性有限自动机 作用 : 非确定性有限自动机并没有增加 自动机 的计算能力 , 但是给自动机设计带来很多方便 ; 仅限于在理论计算时带来很多方便 , 但是无法实现 ;

2 . 自动机实现 : 非确定性有限自动机 ( NFA ) 的的优点是给自动机的设计带来了很多方便 , 但是 只有 确定性的有限自动机 ( DFA ) 才能被实现出来 ;

3 . 自动机等价 : 通过算法可以判定两个确定性的有限自动机是等价的 ,

4 . 自动机优化 : 给定确定性有限自动机 , 可以将该自动机优化 , 得到一个最小的与该 DFA 等价的 自动机 ;

5 . 自动机涉及的两个问题 :

① 优化问题 : 给定一个自动机 , 如何找到一个算法 , 将自动机最小化 ;

② 设计自动机 : 给定一个语言 , 如何找到一个算法 , 根据该语言设计出自动机 ;

6 . 引入正则语言 : 确定性有限自动机 ( DFA ) 与 非确定性有限自动机 ( NFA ) 接受的是相同的语言 , 这个语言就是正则语言 ;

二、正则语言

---

正则语言 : 如果一个语言 存在一个 有限自动机识别 , 那么称该语言是 正则语言 ;

( 这个自动机可以是 确定性有限自动机 , 也可以是 非确定性有限自动机 ; )

设计自动机 :

① 自动机设计要求 : 给定一个语言 , 设计能识别该语言的自动机 ;

② 算法自动设计 : 自动机设计的过程 , 有的很复杂 , 希望能找到一个算法 , 使用该算法实现 自动机的设计 ;

③ 语言特点 : 如果要设计能识别 某语言的自动机 , 那么需要先了解这个语言有什么特点 , 知道这个语言的特点就可以设计 识别该语言的自动机 ;

三、 正则语言运算 ★

---

两种正则语言之间的运算 :

前提 : $A$ 是一种正则语言 , $B$ 是另外一种正则语言 ;

1 . 并运算 ( Union ) : 将 $A,B$ 两个语言并在一起 , 就是将 $A$ 语言的字符串 , 和 $B$ 语言的字符串并在一起就可以 ;

A ∪ B = { x ∣ (    x ∈ A    ) ∨ (    x ∈ B    ) } \rm A \cup B = \{ \quad x \quad | \quad ( \; x \in A \; ) \lor ( \; x \in B \; ) \quad \} A∪B={ x∣(x∈A)∨(x∈B)}

2 . 串联运算 ( Concatenation ) : 将 $A$ 语言的字符串 与 $B$ 语言中的字符串串在一起 , 注意 $A$ 语言字符串在前 , $B$ 字符串在后 ;

A ∘ B = { x y ∣ (    x ∈ A    ) ∧ (    x ∈ B    ) } \rm A \circ B = \{ \quad xy \quad | \quad ( \; x \in A \; ) \land ( \; x \in B \; ) \quad \} A∘B={ xy∣(x∈A)∧(x∈B)}

3 . 星运算 ( Star ) :

A ∗ = { x 1 x 2 ⋯ x k ∣ x i ∈ A } ( 0 ≤ i ≤ k ) \rm A^*= \{ \quad x_1 x_2 \cdots x_k \quad | \quad x_i \in A \quad \} \quad\quad (0 \leq i \leq k) A∗={ x1​x2​⋯xk​∣xi​∈A}(0≤i≤k)

循环计算 :

• 计算本质 : 计算的实质是循环 , 在现实中的计算 , 其本质也是不停的重复循环 , 进行计算 ;

• 计算机作用 : 计算机可以代替重复的计算 ;

• 循环运算抽象 : 星运算实质上是对循环运算的抽象表述 ;

• 自动机计算 : 在有限自动机中 , 可以做循环计算 , 使用 星 计算 实现 循环计算 ;

星运算概念 : $A$ 如果是一种语言 , 将 $A$ 中的有限个字符串 , 串在一起 , 组成的集合 , 称为 $A^{\ast }$ ;

( 有限个字符串的 有限个 是不确定的值 , 可以是 10万 , 100亿 $\cdots$ )

星运算结果集合元素个数 : $A^{\ast }$ 集合的个数是无限的 ;

空字符串 : 这个字符串个数可以取值为 $0$ , 即空字符串 , 空字符串一定属于 $A^{\ast }$

四、语言运算示例 ★

---

语言计算示例 :

① $A$ 语言 : A = { 001 , 10 , , 111 } A = \{ 001 , 10, , 111 \} A={ 001,10,,111}

② $B$ 语言 : B = { ε , 001 } B = \{ \varepsilon , 001 \} B={ ε,001}

1 . 并计算 : 将 $A,B$ 两个语言的集合 , 取 并集 即可 , 计算如下 :

A ∪ B = { 001 , 10 , 111 , ε } \rm A \cup B = \{ 001, 10 , 111 , \varepsilon \} A∪B={ 001,10,111,ε}

2 . 串联计算 : $A$ 语言中的任意字符串 , 与 $B$ 语言中的任意字符串 , 串联在一起 , $A$ 语言中有 $3$ 个字符串 , $B$ 语言中有两个字符串 , 那么串联的结果有 $2\times 3=6$ 个 , 计算过程如下 :

A ∘ B = { 001 , 10 , 111 , 001001 , 10001 , 111001 } \rm A \circ B = \{ 001 , 10, 111 , 001001, 10001, 111001 \} A∘B={ 001,10,111,001001,10001,111001}

3 . 星计算 : $A$ 语言的星计算 , 该集合一定是一个无限的集合 , 如果 $A$ 语言不是空集 , 那么该 $A^{\ast }$ 集合个数是无限的 , 其可以由 $K$ 个字符串组成 , $K$ 取值 $0$ 到无穷大 , $[0,+\infty )$ ;

A ∗ = { ε , 001 , 10 , 111 , ⋯   } \rm A^* = \{ \varepsilon , 001 , 10 , 111 , \cdots \} A∗={ ε,001,10,111,⋯}

五、正则语言封闭性 ★

---

正则语言具有封闭性 , 正则语言组成的集合 , 在并运算 , 串联运算 , 星运算 中 , 都是封闭的 ;

封闭性描述 : $A,B$ 都是正则语言 , $A$ 可以找到一个自动机识别该语言 , $B$ 也可以找到一个自动机识别该语言 , 那么一定可以找到一个自动机 分别可以识别 $A\cup B$ , $A\circ B$ , $A^{\ast }$ 语言 ; ( $3$ 个自动机分别识别 $3$ 种语言 )

若 $A,B$ 两个语言是正则语言 , 那么 $A\cup B$ , $A\circ B$ , $A^{\ast }$ 都是正则语言 ;

$A\cup B$ 语言证明 :

前提条件 :

① 已知自动机 与 语言 : 假设有自动机 $M_1$ 识别语言 $A$ , 自动机 $M_2$ 识别语言 $B$ ;

② 设计的 新自动机 与 语言 : 设计新的自动机 $M$ 识别语言 $A\cup B$ , $A\circ B$ , $A^{\ast }$ ;

六、正则语言封闭性 $A\cup B$ 证明

---

$A\cup B$ 语言证明 :

① 无条件跳转 : 引入一个新的状态 , 这个新的状态 , 接受 $\epsilon$ 即可跳转到 $M_1$ 和 $M_2$ 的开始状态 ;

当自动机 $M$ 启动后 , 进入开始状态 , 不需要进行任何计算 , 会无条件跳转到 $M_1$ 和 $M_2$ 的开始状态 ;

② 新自动机 : 自动机 $M$ 所接受的语言 , 实际上就是 $M_1$ 自动机所接受的语言 $A$ 和 $M_2$ 自动机所接受的语言 $B$ 的并集 , 即 $A\cup B$ ;

七、正则语言封闭性 $A\circ B$ 证明

---

$A\circ B$ 语言证明 :

① 旧的自动机与语言 : 假设有自动机 $M_1$ 识别语言 $A$ , 自动机 $M_2$ 识别语言 $B$ ;

② 新的自动机与语言 : 设计新的自动机 $M$ 识别语言 $A\circ B$ ;

生成新自动机 : 只要引入一个 $\epsilon$ 箭头 , 将第一个自动机 $M_1$ 的接受状态 , 改成非接受状态 , 使用 $\epsilon$ 箭头 , 指向 $M_2$ 的开始状态即可 ;

原状态 : 上面的自动机是 $M_1$ , 语言 $A$ , 下面的自动机 $M_2$ , 语言 $B$ ;

新状态 : 将第一个自动机 $M_1$ 的接受状态 , 改成非接受状态 , 使用 $\epsilon$ 箭头 , 指向 $M_2$ 的开始状态 ;

八、正则语言封闭性 $A^{\ast }$ 证明

---

$A^{\ast }$ 语言 封闭性 证明 : 一个自动机 $M$ 识别 $A$ 语言 , 获取识别 $A^{\ast }$ 语言的自动机 , 只需要将 该自动机 $M$ 的开始状态 与 接受状态 连接起来即可 ;

九、自动机扩展

---

整体思想 :

自动机是一个简单的计算模型 , 在自动机上添加 $2$ 次简单的结构 , 就可以使该计算模型达到计算的极限 , 就是图灵机 ;

计算模型经过逐步扩张 , 达到计算的极限 ;