计算理论学习笔记（一）
确定性有穷自动机（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证正则语言的并、连接、星号运算为封闭的。
证明并运算，加入一个新的起始态，然后空漂到两台DFA的接受态即可。连接运算，将$M_1$中接受态全转为非接受态，然后将其空漂到$M_2$的起始态。星号运算，首先加入一个新的起始态（也是接受态）空漂到$M_1$的起始态，然后再将$M_1$的所有接受态空漂到新加入的起始态即可。
正则表达式（RE）
定义
NFA转成RE
利用法则：用力拉首尾，拓扑变形，以星换圈，以并换多路，逐步减少内态。最后得到就是RE。具体可以参考书上46页的2张图。
RE转成NFA
从最小的子表达式到大一点的子表达式逐步建立，直到获得关于原始表达式的NFA. 所以NFA与RE是等价的.
DFA,NFA与RE三者的关系
三者关系如图所求. 
泵引理
定义
应用泵引理证明非正则语言
上述定义是一个正则语言的必要不充分条件，即如果一个语言是正则语言，则它一定满足泵引理。如果不满足泵引理，一定不是正则语言。 注意： 1. 泵引理只能用来证明非正则语言，不能证正则语言。 2. 泵引理只能将“相等”抽成“不等”，“是”抽成“不是”，不能反过来。可能先利用正则语言的交，并，补运算是封闭的，先进行转换。 下面是一些例子 
另外证明$1^{n^2}$或者$1^{2^p}$这种形式语言，可以在序列中相邻两串长度间隔在不能增大作文章，因为长度间隔的离散性，一定不能满足任意抽取均能满足原语言。