写在前面

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

正文

Lecture3

上下文无关语法 Context Free Grammars(CFGs)

上下文无关法是一种更强大的描述语言的方法
这种语法可以描述具有递归结果的某种特征，使得它们在各种应用中都很有用

一个CFG拥有
1.替换规则substitution rule的集合，也被称作产生式 Productions.
每个规则在语法中显示为一行，包括一个符号和一个用箭头分割的字符串
2.上述的“符号”，我们把它称作变元 variable
3.字符串由变量和其它被叫做“终结符 terminals” 的符号组成

比如有语法G0：
A → 0A1
A → B
B → #
其中，它的变元就是A和B，这里A就是起始变元 start variable
它的终结符是0，1，和#

它可以对左边进行缩写，即：
A → 0A1 | B
B → #

语法生成字符串

1.写下起始变元
2.根据规则来替换变元，重复，直到只剩下终结符terminal
3.我们把产生的字符串称作“结果”
4.L(G)就是所有生成字符串的语言
5.我们称L(G)是一个上下文无关语言 Context Free Language

能用上下文无关法生成的语言被称为上下文语言

我们为了获得一个字符串而进行的一系列替换操作，被称为派生derivation
获取一个字符串的替换序列称为派生

比如对于我们刚才所举例的G0，现在我们尝试对一个字符串000#111应用G0
A ⇒0A1 ⇒00A11 ⇒000A111 ⇒000B111 ⇒000#111
前几步就是将A转换0A1，不断重复，之后再同理A转B，B转#，这部分可以看一下书的示意图
用上述方式生成的所有字符串，构成了该文法的语言 language of the grammar

CFG-Formal Definition

我们通过一个四元组来定义CFG
𝑉 变元的有限集 finite set of variables
Σ 终结符的有限集 finite set of terminal symbols
𝑅 规则的有限集 finite set of rules (rule form: 𝑉→𝑉∪Σ∗)
𝑆 起始变元 start variable

For 𝑢,𝑣∈(𝑉∪Σ)∗ write

𝑢⇒𝑣 如果可以只通过一步来从u转化到v if can go from 𝑢 to 𝑣 with one substitution step in 𝐺,这种情况称作uAv生成yield uwv(设A->w是文法的一条规则)
𝑢⇒𝑣（箭头上面有*）可以通过数步来从u转化到v if can go from 𝑢 to 𝑣 with some number of substitution steps in 𝐺 ，这种情况称为u派生v

如果A = L(G)，其中G是代表一些CFG。那么A就是一个上下文无关语言 Context Free Language (CFL)
先定语法，再生成语言

如果一个字符串有两个不同的解析树，那么它的推导是歧义的，我们说语法是歧义的ambiguous

在描述一个文法的时候，通常只写出它的规则。出现在规则左边的所有符号都是变元，其余符号都是终结符
按照惯例，起始变元就是第一条规则左边的变元

歧义性 Ambiguous

如果文法以不同的方式产生同一个字符串，则称文法歧义地产生这个字符串
如果一个文法歧义地产生某个字符串，则称这个文法是歧义的

一个文法歧义地产生一个字符串的意思是指：该字符串有两棵不同的语法分析树，而不是两种不同的派生
两种不同的派生可能仅仅是替换变元的次序不同，而不是整个结构的不同

为了专注结构，定义一种以固定次序替换变元的派生类型
对于文法G中的一个字符串w的派生，如果在每一步都是替换最左边剩下的变元
则称这个派生是最左派生 leftmost derivation

如果字符串w在上下文无关法G中，有两个或两个以上不同的最左派生，则称G是歧义地(Ambiguously)
如果文法G歧义地产生某个字符串，则称G是歧义的(Ambiguous)

下推自动机 Pushdown Automata PDA

PDA可以从堆栈顶部写入或读出符号外，其操作与NFA类似
它很像NFA，但是有一个称为栈stack的额外设备

PDA在能力上与上下文无关法等价

因此，证明一个语言是上下文无关法时，可以给出生成它的上下文无关文法，也可以给出识别它的PDA

PDA能够把符号写到栈上并在随后读取它，向栈中写入一个符号将其它符号下推
任何时候，也可以读和删去顶部符号，其余符号向上移动

写一个符号：推入Pushing;删除一个符号:弹出Popping

对栈的所有访问，无论读写，都只在栈顶进行

比如我们举例说明D={$0^k1^k$ | k>=0} 的PDA：
1.从输入读取0，推到堆栈上，直到读取1。
2.从输入中读取1s，同时从堆栈中弹出0。
3.如果堆栈为空，则输入accept状态。（注：仅在输入结束时接受）

栈的作用体现在它能够保存无限的信息量

另外，下推状态机可以是非确定的，确定型下推自动机与非确定型下推自动机在语言识别能力上不相同

确定型有穷自动机和非确定型有穷自动机能识别相同的语言，但对下推自动机则不同

形式化定义 Formal Definition

PDA是一个六元组

栈是一个存放符号的设备，这些符号取自某个字母表。机器对于它的输入和栈，可以使用不同的字母表

1.Q是状态集
2.Σ是输入字母表
3.Γ是栈字母表
4.𝛿：Q×Σ×Γ’→𝒫(𝑄×Γ) 是转移函数
5.起始状态q0
6.F属于Q接受状态集

可以参考书中的例2.9来辅助理解
另外，我们也可以使用状态图来描述PDA

CFGs -> PDAs

Thm:如果A是一个上下文无关语言CFL，则一些PDA可以识别A

将A的CFG -> PDA：
1.将起始符号Push到栈中，另外同时也把标记符$放入
2.根据顶部情况处理：
a.Variable:非确定地选择一个关于A的规则，并且把A替换成这条规则右边的字符串
b.Terminal:设它是终结符a,则读取下一个输入符号，并且把它与a进行比较。如果它们匹配，则重复。不匹配则这个非确定性分支被拒绝
3.如果栈为空（也就是顶部是符号$），且之前没有拒绝过，则接受

当且仅当一些PDA可以识别语言A时，我们认为A是一个上下文无关语言CFL

对比一下CFL的情况：

每一个正则语言都是CFL Every regular language is a CFL

如果A是一个CFL，而B是正则的，那么𝐴∩𝐵是一个CFL

证明一个语言不是上下文无关

和正则语言类似，我们利用泵引理来证明一个语言非上下文无关
我们先来看看关于上下文无关语言的泵引理

上下文无关语言泵引理

如果A是上下文无关语言，则存在数p（泵长度），使得A中的任何一个长度不小于p的字符串s，都能被划分为5段，且满足以下条件：

1.对于每一个i>=0。都有$𝑢𝑣^i𝑥𝑦^i<𝑧$∈𝐴
2.𝑣𝑦 ≠ ε 或者说 |𝑣𝑦|>0
3.|𝑣𝑥𝑦| ≤ 𝑝

对于上下文无关语言的泵引理，我们关注的重点在第2、4段

我们可以说，如果A是一CFLs，对于在A中的所有长字符串(Long Strings)都是符合泵引理的(pumpable)

这里以及泵引理的证明可以配合书中的配图更好理解

证明非上下文无关 Proving Non-CF

可以利用例题来理解这部分
由于例题和解答写进MD的难度过大，请直接在书中看

丘奇-图灵论题 The Church-Turing Thesis

有限自动机和下推自动机由于内存有限而无法用作通用计算机的模型
现在，我们转向一个更强大的模型，它首先由艾伦图灵于 1936 年提出，称为图灵机 Turing machine
图灵机是一种更精确的通用计算机模型,它可以做真正的计算机可以做的一切

Turing machine is a much more accurate model of a general-purpose computer. It can do everything that a real computer can do.

Turing Machines TMs

1.头部可以进行读写
2.头部可以往两个方向移动（可以向左或向右）
3.磁带是无限的（向右）
4.无限多个空格“˽”跟随输入
5.可以随时接受或拒绝（不是只能在结尾输入）

为了设计好一个图灵机M1,我们基于读写头作出以下设计：
1.读写头在输出串是多次通过，每一次匹配#两边的一对字符
2.为了记录哪些字符已经被检查过，M1会消去所有已经检查过的符号
3.进行匹配：如果最后所有的符号都被消去，意味着匹配成功，进入Accept状态
3.如果发现一个不匹配的，就直接进入拒绝状态

M1的算法如下：
1.0在#两边的对应位置来回移动。检查这些位置是否包含相同的符号，如果不是，或者没有#，就直接拒绝
1.1为了记录对应符号，消去所有检查过的符号
2.当#左边的所有符号被消去，检查#的右边是否还有符号，如果是，则拒绝。否则进入接受状态

对于 𝐵={$a^k b^k c^k$│ 𝑘≥0} 的图灵机示例

1.向右扫描直到检查到 ˽ ,同时检查输入是否在 $a^k b^k c^k$ 中，如果不是则拒绝，
2.将头返回到左端
3.向右扫描，分别检测单个 a、b 和 c。
4.如果扫描到了某种符号的最后一个，则返回
5.如果扫描到某个符号的最后一个而不是其他符号，则拒绝。
6.如果我们所需的所有符号都存在，则返回第三步

TM的形式化定义

实际中，为了避免过于繁琐。我们实质上很少使用图灵机的形式化描述。

我们使用一个七元组来定义TM
Q:状态集
q0:起始状态
qacc:接受状态
qrej:拒绝状态
Σ：输入字母表 input alphabet
Γ:胶带表 tape alphabet (Σ⊆Γ)
𝛿：Q×Γ→𝑄×Γ× {L, R} (L = Left, R = Right)

图灵机定义的核心是转移函数，它说明了机器如何从一个格局走到下一个格局(“格局”的定义见后)

比如我们输入一个𝑤:
在输入 𝑤 时，TM 𝑀 可能会停止（输入 𝑞“acc”或 𝑞“rej”）或 𝑀 可能永远运行（“循环”）。有以下三种可能
1.接受𝑤(进入qacc)
2.拒绝w，以停止halt来拒绝(进入qrej)
3.拒绝w，以循环looping来拒绝(running foever)

TM-计算

M 接收到它的输入𝒘= 𝒘𝟏 𝒘𝟐 …𝒘𝒏∈ 𝚺∗ 在磁带最左边的 n 个方块上。磁带的其余部分是空白的
（即，填充空白符号 blank symbols），磁带头从磁带最左边的方块开始。
计算根据转换函数 𝛿(𝑞,a)=(𝑟,b,R) 描述的规则进行。
计算一直持续到它进入接受或拒绝状态，此时它停止。
如果两者(accept和reject)都没有发生，则 M 会一直运行下去

图灵机在计算过程中，“当前状态”、“当前子带内容”、“读写头当前位置”，三者结合起来，被称为格局

如果图灵机合法地，从C1格局到达了C2格局，我们就称”C1 产生 yield“ C2

图灵机格局 TM-Configuration

当前状态、当前磁带内容和当前磁头位置的设置称为图灵机的配置 configura of the Turing Machine
对于”𝒖 𝒒 𝒗”,它表示当前状态为𝒒，当前磁带内容为𝒖𝒗
当前磁头,就是𝒗的第一个符号的位置
磁带包含的空白符号blank sybols 只能是的最后的符号(last symbol of 𝒗.)

如果配置序列 C1，C2，…，则图灵机 M 接受输入 w
如果满足下方的条件，则C1,C2…CK存在

C1是M在输入w上的起始格局
每个 Ci 产生 Ci+1
Ck 是一个接受格局 accepting configuration

TM 识别器和决策器 TM Recognizers and Deciders

Def:
Recognizers:𝐴 is Turing-recognizable if 𝐴=𝐿(𝑀) for some TM 𝑀
Deciders:TM 𝑀 is a decider if 𝑀 halts on all inputs
Turing-decidable:𝐴 is Turing-decidable if 𝐴=𝐿(𝑀) for some TM decids 𝑀.

如果一个语言能被某一图灵机识别，则称它是图灵可识别 Turing-recognizable的

我们更喜欢那些“对所有输入的最终结果都是停机”的图灵机，它们不产生循环，我们把它们称为判定器 Decider
如果一个语言能被某一图灵机判定，则称它是图灵可判定的，简称可判定的 decidable

P.S. 一些地方把“图灵可识别的”称为“递归可枚举语言”，把“可判定的”称为“递归语言”

TM例题

由于例题和解答写进MD的难度过大，请直接在书中看
P107-110

多带图灵机 multitape Turing machine

多带图灵机 multitape Turing machine
就像普通的图灵机，不过它有多个磁带，而且每个磁带都有自己的读写头。
转换功能已更改为允许同时读取、写入和移动部分或所有磁带上的磁头

它的转移函数为：
𝛿 = QX$Γ^k$ -> QX$Γ^k$ X $ {L,R,S}^k $

Multitape 图灵机似乎比普通图灵机更强大，但我们可以证明它们在功率上是相同的
换言之，每个多带图灵机都有一个等效的单带图灵机

remind：如果两个ji
(证明过程暂略)

多带图灵机推论

推论：一种语言是图灵可识别的，当且仅当某个多磁带图灵机识别它时
A language is Turing-recognizable if and only if some multitape Turing machine recognizes it.

一个图灵机可识别语言，是由一个普通的（单带）的图灵机识别的,而它是一种多带图灵机的一种特殊情况。
(这证明了这一推论的一个方向。另一个方向遵循书中的定理 3.13)

非确定性图灵机 Nondeterministic Turing machines

非确定性图灵机的转移函数具有以下形式:
Q×Γ → 𝒫(𝑄×Γ×{L,R})

非确定性图灵机的计算和NFA类似，也是一棵”树”，树的不同分支对应于机器的不同可能性

每个非确定性图灵机都有一个等价的确定性图灵机

every nondeterministic Turing machine has an equivalent deterministic Turing machine

推论A：
一种语言是图灵可识别的，当且仅当某个非确定性图灵机识别它时
A language is Turing-recognizable if and only if some nondeterministic Turing machine recognizes it.

推论B:一种语言是可判定的 decidable ，当且仅当某个非确定性图灵机对其进行判定。
A language is decidable if and only if some nondeterministic Turing machine decides it.

Lecture4 图灵机

主要是总结，因为L3写了不少图灵机了

非确定性图灵机 Nondeterministic Turing machines

非确定性图灵机的过渡函数的形式为
Q×Γ → 𝒫(𝑄×Γ×{L, R})

非确定性图灵机的计算是一棵树，其分支对应于机器的不同可能性。

理论：每个非确定性图灵机都有一个等价的确定性图灵机

Theory:every nondeterministic Turing machine has an equivalent deterministic Turingmachine

NTM 推论

推论：当且仅当某些非确定性图灵机识别我时，语言是图灵可识别的
推论：一种语言是可判定的，当且仅当某个非确定性图灵机判定它

枚举器 Enumerator

定义：
枚举器是带有打印机的图灵机。图灵机可以使用该打印机作为输出设备来打印字符串

枚举器是图灵机的一种变形。概略地说，枚举器是带有打印机的图灵机，图灵机把打印机当作输出设备，从而可以打印串

枚举器的计算方式：
1.一个枚举数E从工作磁带上的空白输入开始
2.如果枚举器不停止工作，它可能会打印一个无限的字符串列表
3.E所枚举的语言是它最终打印出来的所有字符串的集合
4.E可以按任意顺序生成语言的字符串，也有可能含有重复

推论：
当且仅当某个枚举器枚举它,一种语言是图灵可识别的

我们想证明这一点，首先证明“如果有枚举器E枚举语言A，则有图灵机M识别A”
我们设计一个图灵机M，它按照下面的方式运行：
M=”对于输入w
1.运行E，每当E输出一个串时，将之与w比较。
2.如果w曾经在E的输出中出现过，则接受”

显然，M接受在E的输出序列中出现过的那些串

现在证明另外一个方向。设s1,s2,s3…是∑*中所有可能的串，
如果图灵机M识别语言A，则A构造枚举器E如下：
E = “忽略输出。
1.对i=1,2,3…重复下列步骤。
2.对s1,s2,s3,…,si中的每一个，M以其作为输入，运行i步
3.如果有计算接受，则打印出相应的$S_j$ “

如果M接受串s,它终将出现在E生成的打印列表中。事实上，它将在此列表中出现无限多次
也每一次重复步骤1,M在每一个串上都从头开始运行。
这个过程有使N在所有可能的输入上并行运行的效果

定义算法 Defn of Algorithm

Church 使用称为 λ 演算的符号系统来定义算法。图灵用他的“机器”做到了这一点。

这两个定义被证明是等价的

算法的非正式概念与精确定义之间的这种联系被称为丘吉尔-图灵论Church–Turing thesis

示例：
LetD = {p|p 是一个具有整数根的多项式}
希尔伯特的第十个问题本质上是问集合 D 是否可判定。答案是否定的

然而，D是图灵可识别的Turing-recognizable

让D1 = {p| p 是 x 上的多项式，有一个整数根}，这是一个识别 D1 的 TM M1

M1 = “在输入 ⟨p⟩ 上：其中 p 是变量 x.1 上的多项式。计算 p，x 依次设置为值 0、1、-1、2、-2、3、-3、…。 . . .如果在任何时候多项式的计算结果为 0，请接受。”

M1 和 M 都是识别器recognizers ，但不是决定器deciders

描述图灵机的术语 Terminology for Describing Turing Machine

形式化描述——图灵机的状态、转移函数等
实现描述–描述图灵机移动头部的方式以及它在磁带上存储数据的方式的英文散文
高级描述–用英语散文来描述一个算法

图灵机符号 Notations for Turing Machine

1.图灵机的输入始终是字符串。字符串可以轻松表示多项式、图形、语法、自动机以及这些对象的任意组合
2.⟨⟩–将一个对象O编码为一个字符串的表示方式⟨1, 2, . …，⟩–对k个对象的编码

Lecture5：Decidability

可判定性
小复习：
𝐴 is T-recognizableif 𝐴=𝐿(𝑀)for some TM 𝑀.
𝐴 is T-decidableif 𝐴=𝐿(𝑀)for some TM decider(halts on all inputs) 𝑀

验收问题 Acceptance Problem

Acceptance Problem for DFAs

Let 𝐴DFA= {<𝐵,𝑤> | 𝐵 is a DFA and 𝐵 accepts 𝑤}
Theorem: 𝐴DFA is decidable

Give TM 𝐷A−DFA that decides 𝐴DFA.

𝐷A−DFA=“On input 𝑠
1.Check that 𝑠has the form <𝐵,𝑤> where 𝐵 is a DFA and 𝑤is a string; rejectif not.
2.Simulate the computation of 𝐵 on 𝑤.
3.If 𝐵ends in an accept state then accept.If not then reject.”

(这部分建议看PDF或者书的例题)

Let $𝐴_TM$ = { <𝑀,𝑤 > | 𝑀 is a TM and 𝑀 accepts 𝑤}
Today’s Theorem: $𝐴_TM$ is not decidable
一些计算问题可以表示成检查语言的成员的隶属关系，证明这个语言是可判定的，与证明这个计算问题是可判定的，是一回事

无穷大的大小 The Size of Infinity

如何比较无限集的相对大小？

如果存在一对一one-to-one和 onto 函数，则说 set 和具有相同的大小f：A → B
one-to-one:单射性injective，即x!=y可以推出f(x)!=f(y)
onto:满映射surjective,Range(f) = B

非正式地讲，如果我们能把两个集合的成员配对起来，那么这两个集合就有相同的大小。这个定义适用于有限集合
现在我们将其应用于无限集合

对于两个有限集合，如果其中一个集合的元素配对，则它们有相同规模

如果存在函数f:A->B,f是一对一映射又是满映射，则称集合A和B有相同规模
而即是一对一映射又是满映射的函数称为对应 correspondence
在对应中，A的每个元素映射到B的唯一一个原色，且B的每个元素都有A的唯一一个元素映射到它
对应就是将A的元素与B的元素进行配对的方法

一对一映射又称为单射injective，对应又称双射bijective

可数集 Countable Sets

如果一个集合是有限的或者它的大小与ℕ相同，那么它就是可数的。

ℤ 和 ℚ+ 都是可数的

证明R(实数集)是不可数的，我们使用对角化Diagonalization
我们利用反证法和对角化来证明，首先我们假设R是可数的

我们只需要找到一个数字，在N->R的映射中无法实现即可
那就是x=0
(证明见书)

R是不可数的推论

Let ℒ=all languages
Let ℳ=all Turing machines

1.ℒ is uncountable
2.ℳ is countable
3.有些语言是不可判定的。因为所有的语言比图灵机能表示的语言多
Some language is not decidable.Because there are more languages than TMs.

有不可数个语言，但是只要可数个图灵机

还原法 The Reducibility Method

利用我们的知识，即TM是不可判定的，来证明其他问题是不可判定的
Use our knowledge that 𝐴TMis undecidable to show other problems are undecidable