cs335计算理论(一)

写在前面

真的痛苦
而且这部分内容对于大二的学生过于晦涩难懂了，而大三大四乃至研究生学生也不至于看这篇博客
所以这一篇文章更适合那些
同在MIEC受苦，且本质快速阅览的学生
如果要一步一步学，建议去观看油管或者B站计算理论的相关视频

正文

CS335 lecture1

Outline

Automata and Language Theory

Computability Theory

Complexity Theory

Book： ntroduction to the Theory of Computation,Sipser, 3rd Edition US

本课程是关于计算理论的，它试图回答以下问题
1.计算机硬件和软件的数学属性是什么？
2.什么是计算，什么是算法？我们能对这些概念给出严格的数学定义吗?
3.计算机的局限性是什么？“一切”都可以计算吗？（这个问题的答案是“不”）

是否可解决
若可以，设计一个算法/模型来解决
选择的方法的复杂度（时间、内存等）怎样

AIM: 开发反映现实世界计算机的计算的正式数学模型

理论知识预备

Set集合

Set是一个单位所代表的对象的集合

1.集合中的对象 Object 被称为集合的元素
2.集合的元素被表现在括号中，不同的元素使用逗号隔开。 {1,a,b,c}
3.一个集合不能有出现重复的元素
4.集合中，元素的顺序并不重要
5.没有元素的集合被称为空集 ∅={}

基本概念与表示

𝑥∈𝐴 ：x是A的一个元素
𝑥 ∉𝐴 ：x不是A中的一个元素
𝐴⊆𝐵 ：A中的每个元素也是B的元素，也就是A是B的一个子集
𝐴⊂𝐵 ：是B的子集，且B中存在A中不存在的元素
𝐴⊈𝐵 ：A不是B的子集

几个比较重要的集合:
ℕ:自然数集，1,2,3…
ℤ：整数集，…,-2,-1,0,1,2…
ℚ:有理数集,{a/b: a,b∈Z,b!=0}
ℝ：实数集
ℂ：复数集

它们之间的层级结构: ℕ⊆ℤ⊆ℚ⊆ℝ⊆ℂ

集合间的运算

-Union: 𝐴∪𝐵={𝑥∶𝑥∈𝐴𝑜𝑟𝑥∈𝐵}
-Intersection: 𝐴∩𝐵={𝑥∶𝑥∈𝐴𝑎𝑛𝑑𝑥∈B}
-Complement:̅𝐴={𝑥∶𝑥∉𝐴}
-SetMinus: 𝐴\𝐵={𝑥∶𝑥∈𝐴 𝑎𝑛𝑑 𝑥∉𝐵}

Cartesian Product 笛卡尔积

AXB代表A、B两个集合的笛卡尔积，结果是来自A的元素a,和来自B的元素b的有序组合，比如

A = {0，1} B = {m,n}
AXB:{(0,m),(0,n),(1,m),(1,n)}

𝐴×𝐵 ≠ 𝐵×𝐴

笛卡尔积也叫做叉积。笛卡尔积产生的集合是“第一个元素为A的元素，第二个元素是B的元素”的所有有序对最初的集合
有序对：二元组

函数以及集合间的函数关系Function

函数function也叫映射mapping，函数是一个建立输入-输出关系的对象，函数又叫映射，f(a) = b ,称f把a映射为b
1.可能输入的集合是“定义域”，可能得到输出的集合是“值域”。如果一个函数取得值域的所有元素，则称它映上onto到这个值域
2.k个自变量的函数被称为k元函数，k就是函数的元数 arity
3.谓词predicate或性质property是一种函数，它的值域为{TURE,FALSE}
4.定义域为&A^k&的谓词称为关系relation 或 k元关系 k-ary relation ,也叫“A上的k元关系”
5.等价关系是一种特殊的二元关系，如果二元关系R满足自反的reflexive 、 对称的symmetric、传递的 transitive，则称他是一个等价关系

自反，每一个x,xRx
对称，每一个x,xRy则意味着yRx
传递，对每一个x、y、z，如果xRy且yRz,那么有xRz

一个由集合A到集合B的函数 f ，是一个AXB（A、B笛卡尔积）的子集

If 𝑎,𝑏∈𝑓 , 𝑓(a)=𝑏.

Strings字符串

基础概念

字母表Alphabet 是一个有限的非空集合，字母表的成员member就是字母表的标志symbols
一个来自alphabet的String（即“字母表上的字符串 string over an alphabet”）就是一个没有逗号，没有分隔符，没有空格的来自字母表的标志组成的序列。(Σ 代表一个字母表)
比如：
a string over Σ={0,1} is 010101001

a string over Σ={𝐴,𝐵,𝐶,⋯,𝑍} is any word,e.g.,COMPUTATION

字符串的长度

𝜀:empty string 空字符串
在代表字符串的字母两侧加上绝对值符号，则代表这个字符串的长度
比如，𝑤=010101001 ，|𝑤|=9
|𝜀|=0

Reverse of string 字符串转置

在代表字符串的字母右上角写上R,代表该字符串的转置
W = 111000
WR = 000111

Wu代表这W和U两个字符串的连接，比如
w = aabba u = bbb
Wu = aabbabbb
Wk(这里是W的k次方)代表着W与自己本身连接了k次，其中W的0次方为 ε

字符串的偏序 Partial Order on Strings

如果存在一个字符串z,使得y = xz ,那么我们则说x是字符串y的一个前缀prefix，而且𝑥⊆𝑦

特别的，如果有𝑥⊂𝑦，那么则称x是y的真前缀proper prefix

语言

若A是机器M接受的全部字符串集，则称A是机器M的语言，记作L(M) = A ，有称作M识别A或者M接受A

一台机器可能接受若干个字符串，但是它永远只能识别一个语言。如果机器不接受任何字符串，那么它仍然识别一个语言，即空语言

语言的串联 Concatenation of Languages

我们假设A和B是两个字母表，则我们可以这样定义A·B 或者 A.B :

𝐴.𝐵={𝑥𝑦:𝑥∈𝐴,𝑦∈𝐵}
次方在这里同样适用，比如:
A^0 = {𝜀}
A^k+1 = A.A^k

克莱恩星 Kleene Star
我们定义A*代表A这个字母表大于等于0次的自由组合，可以类比一下正则表达式

运算与示例

1.对于只有一个字母的字母表，我们常用 a* 代替 {a}*
2.对于A+，它意味着A*\ {𝜀}

我们假设A = {a,b}
$A^0$ = {𝜀}
$A^1$ = A
$A^2$ = {aa,ab,ba,bb}
$A^3$ = {aaa,aab,aba,baa,abb,bab,bba,bbb}
$A^*$ = {𝜀,a,b,aa,ab,ba,bb,…}
$A^+$ = {a,b,aa,ab,ba,bb,…}

语言 language

实质上，任何由字母表Σ展开的语言，实际上都是Σ*的一个子集

比如，Σ = {0,1},此时我们有一个语言A,A = {0,00,00,…} = 0 + ，此时A就是一个由Σ 展开的语言

有限状态机 Finite Automata (有穷自动机)

有限状态机是一个内存有限的，良好的计算机模型，常用于一些控制器上(比如自动门)

输入：有限的字符串
输出：接受或者拒绝
过程：从起始状态 start state 开始，读取输入的标志，遵循已经规定好的、对应的转换原则，最后做出选择：接受或拒绝

形式化定义Formal Definition

一个有限状态机可以分为五个元组
Q：有限的状态集【状态表】
Σ：有限的字母状态集合【字母表】
𝛿：转换 (“比如我们在状态x时读到了1，那么转移到y” 可以表示为“𝛿(x,1) = y”)【转移函数】
$q_0$:起始状态 【起始状态】
F：可接受状态的集合 【接受状态集】

-A stringis a finite sequence of symbols in Σ
-A languageis a set of strings (finite or infinite)
-The empty stringεis the string of length 0
-The empty language ø is the set with no strings

如果某种有限自动机能识别一种语言，那么这种语言就是正则的
A language is regularif some finite automaton recognizes it.

正则运算

设A和B是两个语言，定义正则运算的并、连接、星号 如下
1.并 Union
𝐴∪𝐵= {𝑤| 𝑤∈𝐴 or 𝑤∈𝐵}

2.连接 Concatenation
𝐴∘𝐵={𝑥𝑦 | 𝑥∈𝐴 and 𝑦∈𝐵} =𝐴𝐵

3.星 Star
A* = {x1x2x3…xk | k>= 0 , 且每一个xi∈A} notes:ε∈A

示例

A = {good,bad} B = {boy,girl}

𝐴∪𝐵 = {good,bad,boy,girl}
𝐴∘𝐵 = {goodboy,goodgirl,badboy,badgirl}
A* = {ε,good,bad,goodgood,goodbad,badgood,badbad,…}

正则语言

如果一个语言被一台有穷自动机识别，则称它为正则语言 regular language

正则语言封闭性

一般来说，如果把某种运算应用于一个对象集合的成员，得到的对象依然在这个集合中，那么称这个对象集合在该运算下封闭
正则语言的封闭性如下:

Theorem: 如果A1，A2是正则语言，那么 A1∪A2 也是

Theorem: 如果A1，A2是正则语言，那么 A1A2 也是

Theorem: 如果A1，A2是正则语言，那么 A1∘A2 也是

Theorem: 如果A是正则语言，那么 A* 也是

CS335 lecture2-3

非确定性有限状态机 NondeterministicFinite Automata

正则语言的闭包属性

Thm：如果A1 A2 是正则语言，那么A1A2也是正则语言(closure under ∘)
当M接受x而M2接受y时，M才能接受输入。为了解决“M不知道在什么地方把他们分开”这个问题，我们引入了新的技术
那就是非确定性

来自非确定性nondeterminism的新特性

1.可能会有多个路径，每一次都可能有0，1，多条的情况(在任何一个点，下一个状态都有若干选择)
2.ε-transition(ε)代表着一个“自由” (free) 的输入，意思是可以不读取输入内容就可以进行到下一步
3.Accept input if Accept input ifsomesomepath leads to accept state accept
如果一个输入可以找到一个“到达accept的路径”，那么它就可以被接受

NFA形式化定义

NFA的形式化定义和DFA类似：状态集，输入字母表，转移函数，起始状态，接受状态
关键在于,NFA的转移函数与DFA不同，这导致了它们本质上的不同。
另外，若NFA有k种状态，那么它就要$2^k$个状态子集

我们可以从以下三个方面来认知非确定性：
1.计算机 Computational ： 把非确定性看作若干个独立的线程，若干个子线程中至少有一个被接受，那么整个计算就会被接受
2.数学 Mathematical:想象一个有许多枝干的树。如果任意一个枝干可以到达accept state ，那么我们就选择接受它
3.Magical:猜测每一个不确定的步骤。在有可能的情况下，机器慧选择出一条可以接受的道路(即可以到达 accept state的情况)

将NFAs转化为DFAs

Thm：如果一个NFA 承认recognize A,那么A就是正则的

Every nondeterministic finite automaton has an equivalent
如果两台机器识别同样的语言，则称它们是等价的

每一台非确定型有穷自动机都等价于某一台确定型有穷状态机

正则语言的闭包性

Theorem: 如果A1，A2是正则语言，那么 A1∪A2 也是

正则语言在并运算下封闭

Theorem: 如果A1，A2是正则语言，那么 A1A2 也是

Theorem: 如果A1，A2是正则语言，那么 A1∘A2 也是

正则语言在连接运算下封闭

Theorem: 如果A是正则语言，那么 A* 也是

正则语言在星号运算下封闭

相关证明详见书，写字太抽象了

Regular Expressions →NFA

Thm：如果过R是一个正则表达式，而且A = L(R) ，那么A就是正则的

Thm1:一个语言是正则的，当且仅当有一个非确定型有穷自动机识别它
a.如果有一天NFA能识别这个语言，则它是正则的。
b.仅当，有一台NFA识别这个语言时，它才是正则的

Thm2:一个语言是正则的，当且仅当可以用正则表达式表达它
a.如果一个语言可以用正则表达式描述，那么它是正则的
b.如果一个语言是正则的，则可以用正则表达式描述它
(想要证明B，我们需要引入一个新的概念：广义非确定性有穷自动机，见下文 )

CS335 lecture4

正则表达式及其形式化定义

可以用正则运算符构造描述语言的表达式，称为正则表达式
在正则表达式中，先做星号运算，然后再做连接运算，最后做并运算。用括号可以改变运算顺序

形式化定义
称R是一个正则表达式，如果R是:
1.a,这里的a是字母表中的一个字母
2.ε
3.∅
4.(R1 U R2),这里R1和R2是正则表达式
5.(R1R2),这里R1,R2是正则表达式
6.(R*)，这里的R是正则表达式

其中,第一二条分别表示语言{a},语言{ε}。第三条代表空语言。另外，ε代表只包含一个字符串(空串)的语言，而空集符号就是不包含任何字符串的语言
当想要明显地区分正则表达式和它所描述的语言时，把R描述的语言写作 L(R)

Thm：如果过A是一个正则表达式，对于一些正则表达式，则有A = L(R)

另外，把空集连接到任何集合上，得到的都是空集

把空语言加到任一其他语言上不会改变这个语言
把空串加到任一字符串上不会改变这个字符串
R U ∅ = R R ∘ ε = R

DFAs -> Regular Expressions

Recall Thm : If 𝑅 is a regular expression and 𝐴=𝐿(𝑅) then 𝐴 is regular

如果R是一个正则表达式，而A是该表达式的语言。那么A就是正则的

New Thm: If 𝐴 is regular then 𝐴=𝐿(𝑅) for some regular expr 𝑅
我们想要证明这个，需要引入新的理论——GNFA

广义非确定性有穷自动机 Generalized NFA

Def:广义不确定状态机GNFA 指的是
一种类似于NFA，但是允许使用正则表达式作为转移符号的状态机

广义非确定型有穷自动机就是非确定型有穷自动机，只是转移箭头可以用任何正则表达式作标号。也就是说，GNFA读入的是符号段

为方便起见，我们规定：
1.起始状态有射到每一个其它状态的箭头，但是没有从任何其它状态射入的箭头
2.有唯一的一个接受状态，并且它有从其他每一个状态射入的箭头，但是没有射到任何其它状态的箭头
3.除了起始状态和接受状态，每一个状态到自身和其他每一个状态都有一个箭头

Lemma(引理): Every GNFA 𝐺 has an equivalent regular expression 𝑅

DFAs -> GNFA

添加一个新的起始状态和一个新的接受状态，从新的起始状态到原起始状态有一个ε箭头，从每一个原接受状态到新接受状态有一个ε箭头
如果一个箭头有多个标记，则把它替换成一个标记着原先标记的并集的箭头
最后，在没有箭头的状态之间添加标记∅的箭头

GNFA →Regular Expressions

想要把GNFA转化为正则表达式，我们就需要一步步的化简GNFA的状态数k
显然，k是>=2的，我们不断构造有k-1个状态的GNFA，直到把它化简成只有两个状态
我们设有状态qi,qj,qr,其中qr是我们想要删去的一个状态

在原机器中，如果
1.qi到qr有一个标记为R1的箭头
2.qr到自己有一个标记为R2的箭头
3.qr到qj有一个标记为R3的箭头
4.qi到qj有一个标记为R4的箭头
那么在原机器中从qi到qj的箭头标记为
(R1)(R2)*(R3)U(R4)

证明例见PPT或书

非正则语言 Non-Regular Languages

证明一个语言是正则的，我们需要提供一个DFA
证明一个语言是非正则的，我们需要提供证明PROOF（仅仅说明我们无法找到它的DFA是不足够的）
想要证明非正则性，需要运用一个正则性的定理，我们叫做泵引理 pumping lemma
如果能证明一个语言没有这种性质，则可以保证它不是正则的

泵引理

语言中的所有字符串只要它的长度不小于某个特定的值————泵长度 pumping length ， 就可以被抽取
抽取：每一个这样的字符串1都包含一个字串，把这段子串重复任意次，得到的字符串仍在这个语言中

若A是一个正则语言，则存在一个数p（也就是泵长度），使得，如果s是A中的任一长度不小于p的字符串，那么s可以被分为xyz三段，即s = xyz
而且，满足以下条件
1.对于每一个i >=0,x$y^i$z ∈ A
2.|y|>0
3.|xy|<= p

Informally: 𝐴 is regular → every long string in 𝐴 can be pumped and the result stays in 𝐴.

if 𝑠∈𝐴 and |𝑠|≥𝑝 then 𝑠=𝑥𝑦𝑧 where

1. 𝑥$𝑦^𝑖$𝑧∈𝐴 for all 𝑖≥0
2. 𝑦≠”ε”
3. |𝑥𝑦|≤𝑝

证明非正则性的办法

我们一般以反证法来证明一个语言不是正则语言

𝐷={$0^𝑘$ $1^𝑘$ |𝑘≥0}
1.假设D是一个正则语言
2.通过泵引理，我们可以得到：𝑠=$0^𝑝$ $1^𝑝$∈𝐷
3.而且，泵引理认为可以把s切分为xyz三个部分。而此时
因此，假设是错误的，因此D是非正则的