计算理论 CH2
计算理论 CH2 正则语言和自动机
2.1 Deterministic Finite Automata
一个超市自动门的例子：把一个表格枚举的所有内容转化为了一个直观的状态图
对于我的FA，基础的定义如下：
也就是说，就是一张图，要包含起始状态、最终状态；转移过程看成一个规则，每次在状态q下读到一个string a之后，会根据我的规则进行状态转移
2.1.1 DFA的定义
就是一个更规范的定义，包括了一系列状态（一个起始状态，一些终止状态） 一个字母表，以及状态转移的函数
这个东西有啥用？比方说，我们可以通过定义一系列的规则，使得我的有限状态机可以接受一系列的输入，并且判断其是否属于一种特定的语言
比方说，我想判断的是在{a,b}中，a开头的语言，那我定义规则为：对于起始状态q1,如果输入的字符串开头为a，那么转移到终止状态q2；否则保持在q1不动。这样一来，我输入一个字符串，最终如果在q2结束，那么这个字符串属于这个语言;否则就不属于，这样就可以完成判断的流程。
需要注意的是，为了更严格地说明，我们一般把say yes的判断定义为可以到达接受状态（final state）比如说，上面的例子我可以定义q1不是final state来说明不是a开头的不合法。
另外一个例子：为了让language不包含连续的三个b，我们让三个b连续前进，并且让连续三个b到达的q3状态不是final state即可 
2.1.2 configuration
一个configuration可以理解为是当前读一个字符串的一个快照，其告诉我们当前处于哪个状态，以及未来需要读的字符是什么。 也就是说，一个config.需要包含两部分信息：一个是当前所处的状态q，另一个是剩余的未读字符串w
进一步地，有如下的对于二元关系的定义：
也就是说，只要这两个二元关系可以一步完成转移，那么就符合这个条件
进一步地：
也就是说，两个config.满足这个闭包的二元关系指的是二者之间可以通过有限步的转移到达
我们使用L(M)来表示可以被状态机M接受的所有字符串的集合（也就是组成的语言）
2.2 Nondeterministic Finite Automata
不同的地方就在于描述转移的这个地方不一样：DFA中的状态转移是一个函数，但是NFA的状态转移只要是一个relation即可，也就是说可能有多条转移路径。；另一个区别是NFA可以容忍空转移，也就是在不接受任何输入的情况下进行状态转移。
我们可以证明，NFA与DFA是等价的：由于DFA的要求更严格，因此我们只需要证明另一个方向即可。
也就是说，我们现在要说明，对于每一个NFA都可以相应将其转化为某种样子的DFA。根据上面的区别，我们分别解决以下两个问题即可：
（1）关于多种不确定的转移：比方说一个q0指向两个q1、q2，我们构造一个新的状态{q1,q2}
（2）关于空转移：把一个状态通过空转移可以到达的状态全部合起来
2.2.0 严格的数学证明
首先看一个引理： 
对于E的定义：E(q)得到的是从q可以通过空转移到达的所有状态的集合
recall：熟悉另一个记号L(M)：表示的是被这个机器接纳的语言的集合！
这个引理的证明如下：采用数学归纳法
（0） 当总的字符串只有e的时候，由于在NFA里面，根据E的定义，由于可以从q空转移到p,因此p一定满足在E(q)中；而另一方面，若右边的式子满足，由于在DFA里面，不允许进行e的空状态转移，因此只能P=E(q). 也就是说，这个时候我们构造，直接取P=E(q)则合题
之后的几个部分手写整理了证明如下：
欠NFA与DFA之间的转换！
2.3 FA & Regular Expression
首先回忆一下之前对于正则表达式的定义：
最终我们可以说明：给定一个正则表达式，可以找到一个对应的FA；反过来，给定一个FA，也可以找到一个对应的正则表达式。
证明的思路为：对于正则表达式的各种计算，可以通过FA之间的计算来实现；而对于每一个FA，尝试用机器拓扑的方式来表示语言，再证明其为正则表达式。
一些FA与正则表达式之间的换算关系如下：
但是注意：无穷个正则表达式的并不是正则表达式！ 
这个相当于就是把第二个语言紧接着拼到第一个语言后面，第一个语言的结尾指向第二个语言的开始
2.4 Languages that are and are not regular
要知道什么语言是正则的，首先要知道什么样的语言是非正则的：
总的一个背景如下：一共有不可数无穷个不同的语言，可数无穷个正则语言；因此，一共有不可数无穷个非正则语言
这些语言都是非正则语言；一个直觉就是，比方说要判断a和b数量一样，或者判断a的数量满足某种条件，这些需要“记忆“数量的语言都不是正则语言
介绍一个用来判断非正则语言的pumping theorem：
但是这个定义，一般用来反着用，来判断一个语言是非正则语言：
可以看成一种和人机的博弈过程：也就是说，说明对任意的n，存在一个string w,无论对于w如何分割，总是存在一个i，使得xyiz不属于这个语言
但是，这个是充分条件 ；也就是说，就算找不出来，也不能判断其不是正则的。