自动机理论

概念

最简单的非平凡有穷自动机是两相开关。

形式化命题

求助于定义

借助定义，表达为数学语言。

$S$ 是有穷的 $\leftrightarrow$ 存在整数 $n$，使得 $||S||=n$。

带量词的命题

当且仅当命题

表示为 A iff B。符号：$A \equiv B$ 和 $A \leftrightarrow B$。

注意证明当且仅当的“当”部分和“仅当”部分。

隐含条件的命题

其他定理形式

如果 $H$ 则 $C$。

1. $H$ 蕴含 $C$。意为能够推出。
2. $H$ 仅当 $C$。
3. $C$ 当 $H$。

其他的证明形式

关于集合的命题

如何证明集合等价？

$E=F \equiv$ $E$ 表示的集合中的每个元素都属于 $F$ 所表示的集合，$F$ 表示的集合中的每个元素都属于 $E$ 所表示的集合。

证明并运算的交换律

$E=R\cup S,F=S\cup R$。

说明 $E=F$。

证明 $R \cup (S \cap U)=(R \cup S)\cap (R \cup T)$

对于元素 $x \in R \cup (S \cap U)$。

由并集的定义，得 $x$ 属于 $R$ 或 $S \cap U$，$x$ 属于 $R$ 或同时属于 $S , U$。

那么 $x$ 属于 $R \cup S$，$x$ 属于 $R \cup T$，$x$ 属于 $(R \cup S) \cap (R \cup T)$。

反之亦然。

逆否命题

如果 $H$ 则 $C$ $\equiv$ 如果非 $C$，则非 $H$。

讨论四种情况：

$C$ 真 $H$ 真，$C$ 真 $H$ 假，$C$ 假 $H$ 真，$C$ 假 $H$ 假。

如果 $H$ 则 $C$ 说明了而 $C$ 假 $H$ 真不存在，其他三种为真。

如果非 $C$，则非 $H$ 说明了 $C$ 假 $H$ 真不存在，其他为真。

说明命题等价。

反证法

如果 $H$，则 $C$ $\equiv$ $H$ 与非 $C$ 同时存在导致矛盾。

归纳证明

1. 基础，对一些较小的整数，证明 $S(i)$ 为真。
2. 归纳步骤，假设 $n \ge i$，其中 $i$ 是基础整数，证明“如果 $S(n)$，则 $S(n+1)$”。

归纳法原理：如果证明了 $S(i)$，以及对于所有 $n \ge i$，$S(n)$ 蕴含 $S(n+1)$，则对于所有 $n \ge i$，$S(n)$ 成立。

更加一般的整数归纳法

结构归纳法

树的递归定义

1. 基础，单个顶点是树，这个定点是树的跟。
2. 归纳，设 $T_1,T_2, \cdots, T_k$ 都是树，连接新节点 $N$ 与这些树的根，能够构造出一棵以 $N$ 为根的新树。

表达式的递归定义

1. 基础，任意数或者字母都是表达式
2. 归纳，$E$ 和 $F$ 是表达式，则 $E+F$，$E*F$ 和 $E$ 都是表达式。

如何证明结构归纳法的正确性，找到最小的错误的表达形式 $E_n$，则对于所有的 $S(E_i),i \le n-1$，结论都是正确的，但是$S(E_n)$ 蕴含于 $S(E_{a_j}),1 \le j \le k$，所以矛盾。

互归纳法

总结

1. 基础和归纳必须分别证明
2. 如果命题是“当且仅当”，必须证明两个方向。

自动机理论的中心概念

1. 字母表，$\Sigma$ 表示，是符号的有穷非空集合。

2. 串，有时称为单词，空串 $\varepsilon$ 和串的长度 $|w|$。

3. 字母表的幂：定义 $\Sigma ^k$ 是长度为 $k$ 的串的集合，串的每个符号都属于 $\Sigma$。

​ $\Sigma^0=\{\varepsilon\},\Sigma \not= \Sigma^1$

​ $\Sigma^* = \Sigma^0 \cup \Sigma ^1\cup \Sigma^2\cup \cdots$（克林闭包）

​ $\Sigma^+=\Sigma^*/\{\varepsilon\}$（闭包）

4. 串的连接：$\varepsilon w= w\varepsilon=w$。

5. 语言：$L \subseteq \Sigma^*$，则 $L$ 是 $\Sigma$ 上的语言。

   空语言 $\varnothing$ 是任意字母表上的语言。

6. 问题：判断一个给定的串是否属于某个具体语言。

   $L$ 是 $\Sigma$ 上的语言，问题 $L$ 就是：给定 $\Sigma^*$ 中的一个串 $w$，判定 $w$ 是否属于 $L$。

有穷自动机

介绍“正则语言”

关键区别：控制是确定的还是非确定的。

"封闭"性和“判定”性。

状态“记住”某些重要事件已经发生而其他事件还没有发生。

重要的是发生怎样的事件序列。

乘积自动机

两个不同自动机的关联。

确定型有穷自动机 DFA

$A=(Q,\Sigma,\delta,q_0,F)$

接受某个地方存在 01 序列的 0/1 串

转移图和转移表

DFA 的语言

$L(A)=\{w|\hat\delta(q_0,w) \in F \}$

该章习题

习题 2.2.2

1. 基础，$|y|=1$，$\hat\delta(q,xy)=\hat\delta(\hat\delta(q,x),y)$ 相当于 $\hat\delta(q,xa)=\hat\delta(\hat\delta(q,x),a)$ 即 $\delta$ 函数的定义。

2. 归纳，$|y|\ge2$ ，则 $y=za$，对于 $|z|=|y|-1$，结论是成立的。

   $\begin{aligned} \hat\delta(q,xy)&=\hat\delta(q,xza)\\ &=\hat\delta(\hat\delta(q,xz),a)\\ &=\hat\delta(\hat\delta(\hat\delta(q,x),z),a)\\ &=\hat\delta(\hat\delta(q,x),za)\\ &=\hat\delta(\hat\delta(q,x),y) \end{aligned}$

习题 2.2.3

只要替换一下，然后由定义有 $\delta(q,a)=\hat\delta(q,a)$……

习题 2.2.4

……

习题 2.2.9

b) 如果 $x$ 是属于 $L(A)$ 的非空串，则对所有 $k>0$，$x^k$ 也属于 $L(A)$

$\hat \delta (q_0,x)=q_f$，又由 a) 有 $\hat\delta(q_f,x)=\hat\delta(q_0,x)=q_f$。

则 $\hat\delta(q_0,x^k)=\hat\delta(\hat\delta(q_0,x),x^{k-1})=\hat\delta(q_f,x^{k-1})$。

由归纳法可知 $\hat\delta(q_0,x^k)=q_f$，即 $x^k \in L(A)$。

非确定性有穷自动机 NFA

区别是 $\delta$ 可以是一个集合，也可以为空，代表线程“多开、死亡“。

$\delta$ 的扩展

1. 基础 $\hat\delta(q,\varepsilon)=\{q\}$。

2. 归纳，$w=xa$，$\hat\delta(q,x)=\{p_1,p_2,\cdots,p_k\}$。

   $\hat\delta(q,w)=\cup_{i=0}^k\delta(p_i,a)$

总结：结构化的递归。

$L(A)$ 的定义

$L(A)={w|\hat\delta(q_0,w)\cap F\not=\varnothing}$

DFA 和 NFA 的等价性

子集构造：$\delta_D(S,a)=\cup_{p\in S}\delta_N(p,a)$

本质是将每个子集看成一个元素。