Theory of computation
导航 introduction chapter1 Sets,relations,and languages 1.4 Finite and infinite sets
Countable Infinite:
一个集合如如果是可数无穷的等价于它与正整数集等势
可数个可数无穷集合是可数无穷的
Cantor’s Theorem
Let f be a map from set A to its power set $P(A)$.Then card(A)$\le$card(P(A)) holds for any set A.(card为元素数量)
证明构造基于讨论是否存在满射，需要构造一个很特殊的集合进行证明:$B={x \in A | x \notin f(x)}$，再通过反证法进行证明。
1.5 Three Fundamental Proof Tech.
The Principle of Mathematical Induction
The Pigeonhole Principle
The Diagonalization Principle
Let R be a binary relation on a set A,and let D,the diagonal set for R,$D = {a | a \in A \land (a,a) \notin R}$. For each $a \in A$,let $R_a = {b | (a,b) \in R}$
Then D is distinct from $R_a$.
上述的principle能够比较直观的证明cantor定理。将映射具象为上述的矩阵表示。可以发现之前的集合B的构造就和上面的D集合的构造相同。
1.6 closure 1.7 Alphabet and Language
Alphabet
Any finite set is called an alphabet.Elements of an alphabet are called symbols.
Strings
we call finite sequences of the alphabet $\Sigma$ words or strings over $\Sigma$
we denote by e the empty string over $\Sigma$
Language: Set of Strings
Alphabet:$\Sigma$
The set of all strings:$\Sigma^* = {e,a,ab,abc,abcd,….}$
Language:$L$
Finite Language:by listing all the strings
Infinite Language:specify by the following scheme:$L = {w \in \Sigma^* | w has property P}$
1.8 finite representation of languages
regular expression
正则表达式构建于字母表上的基本元素和三种核心运算
基本元素:a(字母表中的任意一个符号)，空集。空字符串e
三种核心运算
连接:语言$L_1L_2 = {w_1w_2 | w_1 \in L_1 \land w_2 \in L_2}$
联合:包含$R_1,R_2$描述的所有字符串
Kleene:表示R描述的字符串连接零次或多次
正则表达式的运算规则
chapter2 Regular language and automata 2.1 Determinitic Finite Automata
定义:A deterministic finite automata (DFA) is a
A configuration of a DFA 𝐾, Σ, 𝛿, 𝑠, 𝐹 is in 𝐾 × Σ∗
配置 ∈K×Σ∗：一个配置是一个有序对 (q,w)，其中 q∈K当前状态，而 w∈Σ∗是待处理的剩余输入字符串。
A configuration of a finite automaton 𝑴 tells the current state and the inputs to be read in the future
单步转移关系 (⊢M) 的定义
自动机 M 可以从配置 (q,w) 一步转移到配置 (q′,w′)，当且仅当：输入消耗：待处理的字符串 w 可以分解为一个输入符号a∈Σ 和剩余部分 w′，即 w=aw’。状态转移： 当前状态 q 在读入输入符号 a 后，根据转移函数 δ 移动到新的状态 q′，即 δ(q,a)=q′。
2.2 Nondeterministic Finite Automata
定义:与前面的确定性finite automata最大的区别如下:Δ :transition relation, is thesubset of 𝐾 × (Σ ∪ {𝑒} )× K
等价的定义:两台有穷自动机$M_1$,$M_2$等价，当且仅当$L(M_1)=L(M_2)$,L(M)是自动机M接受的字符串的集合
定理2.2.1:对于每一台非确定性有穷自动机，有一台等价的确定型有穷自动机
证明思路:因为非确定性有穷自动机的特点，所有的状态应该作为状态集合来看待，也就是说从某个开始状态读了字符串后能达到唯一的状态集合，而不是这个集合的某一个不确定成员，构造等价的确定型有穷自动机就是把这个想法形式化。$M^\prime$的状态集合为$K^\prime$，其中$K^\prime$为$K$的幂集;$M^\prime$的终结状态集合由K中至少包含M的一个终结状态的所有子集组成。而对于$M^\prime$的转移函数的定义，我们在形式化之前需要引入以下的关键概念。
对于任一状态$q \in K$,令$E(q) = { p \in K:(q,e)⊢M (p,e)}$，有了上述的概念，我们就能形式化地定义与M等价的确定型有穷自动机$M^\prime$的转移函数。
对于每一个$Q \subseteq K$和$a \in \Sigma$，定义$\delta ^ \prime (Q,a) = \bigcup${$E(p):p \in K 且对某个q \in Q ,(q,a,p)\in \Delta$}
下面提出一个最关键的断言:对任一字符串$w \in Σ^*$和任意状态 $p,q \in K$,$(q,w)⊢M(p,e)$当且仅当对某个包含p的集合P,$(E(q),w)⊢M’(P,e)$。根据这个断言我们来证明等价:考虑任一字符串w,根据定义$w \in L(M)$当且仅当对某个$f \in F$,$(s,w)⊢M(f,e)$;那么根据上面的断言我们知道当且仅当对某个包含f的Q,$(E(s),w)⊢M’(Q,e)$,换句话说，当且仅当对某个$Q\in F^\prime$,$(s^\prime,w)⊢M’(Q,e)$,这就是$w \in L(M^\prime)$的定义，那么我们根据断言成功证明等价。
下面进行断言的证明:
我们使用归纳假设进行证明
基础步骤,|w|=0时，此时第一个命题等价于$p \in E(q)$,又因为$M^\prime$是确定型的，所以第二个命题等价于P=E(q),且$p \in P$,则可说明这两个命题等价。
归纳假设:假设对于某个k，当字符串长度小于等于k时假设成立。要证明对任意长度为k+1的字符串w=va,断言成立。
从左到右:设$(q,w)⊢M(p,e)$,那么存在状态r1,r2使得$(q,w)⊢M(r1,a)⊢M(r2,e)⊢M(p,e)$。也就是有$(q,v)⊢M(r1,e)$,因为|v|=k,由归纳假设知道对某个包含r1的集合R1,$(E(q),v)⊢M’(R1,e)$.由于$(r1,a)⊢M(r2,e)$，根据$M’$的构造$E(r2) \subseteq \delta ^ \prime (R1,a)$,同样有$p \in E(r2)$,因此$p \in \delta ^ \prime (R1,a)$，那么根据$M’$的定义:$(R1,a)⊢M’(P,e)$,进而有$(E(q),va)⊢M’(R1,a)⊢M’(P,e)$得证。
从右到左:证明思路类似。
2.3 有穷自动机与正则表达式
定理2.3.1:有穷自动机接受的语言类在下述运算下是封闭的。
本文总阅读量
