确定性有穷自动机（DFA）

定义

计算理论学习笔记（一）

注意：允许没有接受状态，此时接受语言为空集；转移函数对每一个状态和每一个可能的输入都恰好指定了一个状态。

计算理论学习笔记（一）

定义正则运算的并、连结和星号

计算理论学习笔记（一）

正则运算的并，连结和星号都是封闭的，后面在证明DFA与NFA等价后，会用NFA对其进行证明。

常见语言的DFA状态图举例

计算理论学习笔记（一）

c题含某子串，首先画出对应的子串，然后再判断其它输入的状态转换即可。
f题不含某个子串，首先画出含某个子串的DFA，然后将接受态转为非接受态，将非接受态转为接受态。这里运用了DFA的补是封闭这一性质。
计算理论学习笔记（一）

对于l这种类型的题即DFA的或和且运算，画图比较麻烦，有时采用横1纵0不失为一种好方法。
对于n的倍数余m，首先画出n个状态围成的圈，然后从起始状态数起，将第m个状态标为接受态即可。对于这道题有个变形。画出长度除以3余2且除以4余1的DFA，这里先用中国剩余定理求出长度规律为 $12n+5(n = 0, 1, \cdots,)$ 也就是画出长度除以12余5的DFA。

注意：DFA一般不能对保证串中字符a与字符b相等，如 $a^nb^n$ 不是正则语言，通过后面学习知道它是上下无关语言。但是它能表示一个很特殊的串，即串中01和10子串个数相等，它等价于串以相同的字符开始和结尾。（可以把01和10想象成波形图中的下升与下降，现在下升段与下降段相等，那么开始与结尾的值一定相等，同为0或同为1），DFA如图。
计算理论学习笔记（一）

非确定性有穷自动机（NFA）

NFA与DFA的不同：

一入多出。NFA中一个状态对于每个符号可能有0个，1个或多个转换的箭头。而DFA中每一个状态对于每个符号有唯一的转换箭头（状态转换）
加入空漂。NFA的输入字符比DFA多了一个 $\epsilon$ ，即空漂。

定义

计算理论学习笔记（一）
与DFA的定义同为五元组，但仍存在一定差异。 $\Sigma$ 中新增了 $\epsilon$ ； $\delta$ 的映射结果属于状态集的幂集，即一入多出，同一个符号，可能对应多个状态转换。

注意：由于NFA加入非确定性，一个输入产生了多条路径，只要求所有路径中至少有一条路径能到达接受状态即可，这点与DFA也有所不同。

DFA与NFA的等价性。

首先DFA是特殊的NFA，即一入一出，没有空漂的NFA。
下面主要是将一个NFA转换成与之对应的DFA。
计算理论学习笔记（一）
已知 $DFA\space A = \lbrace Q,\Sigma, \delta, q_0, F\rbrace$ ，现在要构造出一台与之对应的 $NFA\space B = \lbrace Q^{\prime},\Sigma^{\prime}, \delta^{\prime}, q_0^{\prime}, F^{\prime}\rbrace$
首先原来的DFA有n个状态，那NFA有 $2^n$ 个状态（即状态的组合） $Q^{\prime} = \lbrace Q_{00\dots0}, Q_{10\dots0},\cdots,Q_{11\dots1}\rbrace$ ， $\Sigma^{\prime}$ 很简单就为 $\lbrace0,1\rbrace$ ， $\delta^{\prime}$ 要随 $Q^{\prime}$ 相应的改变，多个状态经过相同的输入的结果要进行位与，最后接受态 $F^{\prime}$ 含有 $2^{n-1}$ 即只是含 $q_1$ 即可（第一个二进制位为1）。这样就构造出一台DFA与NFA对应。
即证DFA与NFA是等价的。

NFA证正则语言的并、连接、星号运算为封闭的。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uPuheDn8-1578217863559)(http://onwaier.com/wp-content/uploads/2020/01/22d15579c085b4a803186360f11cc93a.png)]
证明并运算，加入一个新的起始态，然后空漂到两台DFA的接受态即可。连接运算，将 $M_1$ 中接受态全转为非接受态，然后将其空漂到 $M_2$ 的起始态。星号运算，首先加入一个新的起始态（也是接受态）空漂到 $M_1$ 的起始态，然后再将 $M_1$ 的所有接受态空漂到新加入的起始态即可。