计算理论---正则语言全

6
计算模型—上下文无关文法
上下文无关文法：是一个 4 元组 ( V, , R, S )
(1) V 是一个有穷集合，称为变元集。 (2) 是一个与 V 不相交的有穷集合，称为终结符集。 (3) R 是一个有穷规则集，每条规则由一个变元和一个由变元及终结 符组成的字符串构成。 (4) SV 是起始变元。
L 类 NL 类、 NL 完全性、 NL 等于 coNL
17
复杂性理论—难解性
层次定理的含义：定理中的每一个都能证明时间和空间复杂性类不全 相同，它们形成了一个层次结构，其中时空界限较大的类比时空界限 较小的类包含更多的语言。 相应的概念和结论 在相对化方法中，将修改计算模型，给图灵机一些本质上是“免费” 的信息。依据实际提供给它的信息，图灵机就可能比以前更轻松地解 决某些问题。 电路复杂性 布尔电路、电路族、…… 3SAT 是 NP 完全的
SPACE(f(n)) ={ L | L是被 O(f(n)) 空间的确定型图灵机判定的语言}
NSPACE(f(n)) = { L | L是被 O(f(n)) 空间的非确定型图灵机判定的语言} 萨维奇定理：对于任何函数 f : NR+ ，其中 f(n) n，NSPACE( f(n) ) SPACE( f 2(n) )。 P NP PSPACE=NPSPACE EXPTIME PSPACE完全的、 PSPACE难的 TQBF={< >| 是真的全量词化的布尔公式} PSPACE 完全的
15
复杂性理论—时间复杂性
NP中问题举例。
CLIQUE = { <G, k > | G 是包含 k 团的无向图} SUBSET-SUM
NP完全性： NP 中的某些问题的复杂性与整个类的复杂性 相关联。这些问题中任何一个如果存在多项式时间算法，那 么所有 NP 问题都是多项式时间可解的。 语言 A 称为多项式时间映射可归约到语言 B，记为A≤pB， 若存在多项式时间可计算函数 f : **，对于每一个 w， 有 w∈A f(w)∈B。 如果语言 B 满足下面两个条件，就称为NP完全的：

计算机考博试题计算理论及答案计算理论字母表：⼀个有穷的符号集合。

字母表上的字符串是该字母表中的符号的有穷序列。

⼀个字符串的长度是它作为序列的长度。

连接反转Kleene星号L* ，连接L中0个或多个字符串得到的所有字符串的集合。

有穷⾃动机：描述能⼒和资源极其有限的计算机模型。

有穷⾃动机是⼀个5元组M=(K,∑,δ,s,F),其中1）K是⼀个有穷的集合，称为状态集2）∑是⼀个有穷的集合，称为字母表3）δ是从KX∑→K的函数，称为转移函数4）s∈K是初始状态5）F?K是接收状态集M接收的语⾔是M接收的所有字符串的集合，记作L(M).对于每⼀台⾮确定型有穷⾃动机，有⼀台等价的确定型有穷⾃动机有穷⾃动机接受的语⾔在并、连接、Kleene星号、补、交运算下是封闭的。

每⼀台⾮确定型有穷⾃动机都等价于某⼀台确定型有穷⾃动机。

⼀个语⾔是正则的当且仅当它被有穷⾃动机接受。

正则表达式：称R是⼀个正则表达式，如果R是1）a，这⾥a是字母表∑中的⼀个元素。

2）ε，只包含⼀个字符串空串的语⾔3），不包含任何字符串的语⾔4)(R1∪R2),这⾥R1和R2是正则表达式5）(R10R2),这⾥R1和R2是正则表达式6）(R1*),这⾥R1*是正则表达式⼀个语⾔是正则的当且仅当可以⽤正则表达式描述。

2000年4⽉1、根据图灵机理论,说明现代计算机系统的理论基础。

1936年，图灵向伦敦权威的数学杂志投了⼀篇论⽂，题为《论数字计算在决断难题中的应⽤》。

在这篇开创性的论⽂中，图灵给“可计算性”下了⼀个严格的数学定义，并提出著名的“图灵机”(Turing Machine)的设想。

“图灵机”不是⼀种具体的机器，⽽是⼀种思想模型，可制造⼀种⼗分简单但运算能⼒极强的计算机装置，⽤来计算所有能想像得到的可计算函数。

这个装置由下⾯⼏个部分组成：⼀个⽆限长的纸带，⼀个读写头。

（中间那个⼤盒⼦），内部状态（盒⼦上的⽅块，⽐如A,B,E,H），另外，还有⼀个程序对这个盒⼦进⾏控制。

第一章1.1 图给出两台DFA M1和M2的状态图. 回答下述有关问题.a.M1的起始状态是q1b.M1的接受状态集是{q2}c.M2的起始状态是q1d.M2的接受状态集是｛q1，q4｝e.对输入aabb,M1经过的状态序列是q1，q2，q3，q1，q1f.M1接受字符串aabb吗？否g.M2接受字符串ε吗？是1.2 给出练习2.1中画出的机器M1和M2的形式描述.M 1=(Q1,Σ,δ1,q1,F1) 其中1）Q1={q1,q2,q3,};2）Σ={a,b}; 3）δ1为：4）q1是起始状态5）F1={q2}M2=(Q2,Σ,δ2,q2,F2) 其中1）Q2={q1,q2,q3,q4};2）Σ={a,b}; 3）δ2为：3）q2是起始状态4）F 2={q 1,q 4}1.3 DFA M 的形式描述为 ( {q 1，q 2，q 3，q 4，q 5}，{u,d},δ,q 3，{q 3}),其中δ在表2-3中给出。

试画出此机器的状态图。

1.6 画出识别下述语言的DFA 的状态图。

a){w | w 从1开始以0结束}b){w | w 至少有3个1}c) {w | w 含有子串0101}d) {w | w 的长度不小于3，且第三个符号为0}e) {w | w 从0开始且为奇长度，或从1开始且为偶长度}或f) {w | w 不含子串110}g) {w | w 的长度不超过5}1个1}k) {ε,0}0,11l) {w | w 含有偶数个0，或恰好两个1}m) 空集n) 除空串外的所有字符串1.7 给出识别下述语言的NFA a. {w | w 以00结束}，三个状态b. 语言｛w | w 含有子串0101，即对某个x 和y ，w=x0101y ｝，5个状态.c. 语言｛w | w 含有偶数个0或恰好两个1｝，6个状态。

d. 语言｛0｝，2个状态。

e.语言0*1*0*0，3个状态。

f. 语言{ε}，1个状态。

练习1.1 图给出两台DFA M 1和M 2的状态图. 回答下述有关问题.a. M 1的起始状态是q 1b. M 1的接受状态集是{q 2}c. M 2的起始状态是q 1d. M 2的接受状态集是｛q 1，q 4｝e. 对输入aabb,M 1经过的状态序列是q 1，q 2，q 3，q 1，q 1f. M 1接受字符串aabb 吗？否g. M 2接受字符串ε吗？是1.2 给出练习2.1中画出的机器M 1和M 2的形式描述.M 1=(Q 1,Σ,δ1,q 1,F 1) 其中1）Q 1={q 1,q 2,q 3,};2）Σ={a,b};3415）F 1={q 2}M 2=(Q 2,Σ,δ2,q 2,F 2) 其中1）Q 2={q 1,q 2,q 3,q 4};2）Σ={a,b};3324）F 2={q 1,q 4}1.3 DFA M 的形式描述为 ( {q 1，q 2，q 3，q 4，q 5}，{u,d},δ,q 3，{q 3}),其中δ在表2-3中给出。

试画出此机器的状态图。

d1.6 画出识别下述语言的DFA 的状态图。

a){w | w 从1开始以0结束}b){w | w 至少有3个1}c) {w | w 含有子串0101}d) {w | w 的长度不小于3，且第三个符号为0}e) {w | w 从0开始且为奇长度，或从1开始且为偶长度}或f) {w | w 不含子串110}g) {w | w 的长度不超过5}h){w | w 是除11和111以外的任何字符}i){w | w 的奇位置均为1}j) {w | w 至少含有2个0，且至多含有1个1}k) {ε,0}l) {w | w 含有偶数个0，或恰好两个1}0,1 1m) 空集 n) 除空串外的所有字符串1.7 给出识别下述语言的NFA ，且要求符合规定的状态数。

a. {w | w 以00结束}，三个状态b. 语言｛w | w 含有子串0101，即对某个x 和y ，w=x0101y ｝，5个状态.c. 语言｛w | w 含有偶数个0或恰好两个1｝，6个状态。