下载文档原格式
计算理论考研题目及答案### 计算理论考研题目及答案#### 题目一：确定性有限自动机（DFA）的定义和性质问题描述：给定一个确定性有限自动机（DFA）M，其状态集合为Q={q0, q1, q2}，字母表为Σ={a, b}，转换函数为δ，初始状态为q0，接受状态集合为F={q1, q2}。
请根据以下转换函数定义，判断字符串"aba"是否被M接受。
转换函数定义如下：- δ(q0, a) = q1- δ(q0, b) = q0- δ(q1, a) = q2- δ(q1, b) = q1- δ(q2, a) = q2- δ(q2, b) = q0答案：首先，根据转换函数，我们从初始状态q0开始，逐个读取字符串"aba"中的字符：1. 读取字符'a'，应用转换函数δ(q0, a)，状态变为q1。
2. 继续读取字符'b'，应用转换函数δ(q1, b)，状态变为q1。
3. 最后读取字符'a'，应用转换函数δ(q1, a)，状态变为q2。
由于状态q2是接受状态，因此字符串"aba"被DFA M接受。
#### 题目二：图灵机的停机问题问题描述：考虑一个图灵机T，其输入为一个二进制字符串。
请证明图灵机T是否能够解决以下问题：给定一个二进制字符串，判断该字符串是否能够被T在有限步内停机。
答案：这个问题是著名的停机问题，它是一个不可解问题。
根据图灵的停机问题的不可解性定理，不存在一个通用的算法来判断任意给定的图灵机和输入字符串是否停机。
因此，不能构造一个图灵机来判断所有图灵机的停机问题。
#### 题目三：P vs NP问题问题描述：简述P vs NP问题，并给出一个NP完全问题的例子。
答案：P vs NP问题是计算理论中的一个核心问题，它询问：所有那些可以快速验证解的问题（NP问题），是否也能快速找到解（即是否属于P类问题）。
计算机理论基础试题及答案计算机理论基础是计算机科学的基础课程之一，它涵盖了计算机的结构、功能、算法、数据结构等方面。
以下是一些计算机理论基础的试题及答案，供大家学习参考。
试题1.二进制数101101转换成十进制数是多少？2.请简述计算机CPU的工作原理。
3.什么是递归算法？请写出一个简单的递归函数。
4.请解释堆和栈的概念以及它们的区别。
答案1.二进制数101101转换成十进制数的计算方法是：12^5 + 02^4 +12^3 + 12^2 + 02^1 + 12^0 = 45。
2.CPU是计算机的核心部件，它主要负责指令的执行和运算处理。
CPU按照指令的顺序依次读取并执行指令，其中指令包括算术运算、逻辑运算、数据传输等操作。
CPU通过总线与内存、输入/输出设备等其他部件进行数据交换和信息传输，从而完成计算机的计算和控制功能。
3.递归算法是指在函数定义中调用函数本身的算法。
递归算法的特点是问题规模逐步减小，直到达到基本情况。
一个简单的递归函数示例：def factorial(n):if n ==1:return1return n * factorial(n-1)该函数用于计算阶乘，当n等于1时，返回1，否则返回n与factorial(n-1)的乘积。
4.堆和栈都是用于存储数据的数据结构。
堆和栈的区别如下：•堆是动态数据结构，由于堆是动态增长的，所以在任何时候都可以从堆中申请或释放内存，堆中的数据可以随意存储、读取和修改。
•栈是静态数据结构，其大小和存储数据的位置已经预定好了，不能随意增加和删除数据。
栈一般被用于函数的调用过程中，每次调用函数时，函数的参数、返回值、局部变量等数据将被存储在栈中。
•堆和栈的存储方式也不同。
栈是一种数据结构，遵循先进先出（FILO）的原则，新元素通常被添加到栈的顶端，并从顶端删除；堆则是一棵树形结构，其中每个节点都有一个或多个子节点。
节点的添加和删除是基于堆排序规则的。
2024年研究生考试考研计算机学科专业基础(408)复习试题(答案在后面)一、单项选择题（本大题有40小题，每小题2分，共80分）1、下列关于冯·诺依曼体系结构的叙述中，正确的是：A. 计算机由运算器、控制器、存储器、输入设备和输出设备五大部件组成。
B. 指令和数据存放在不同的存储器中。
C. 冯·诺依曼体系结构的计算机硬件系统分为运算器、显示器和键盘三大部分。
D. 程序指令存储在内存中，但数据不能存储在内存中。
2、在计算机内部，数据通常采用哪种形式表示？A. 十进制B. 八进制C. 十六进制D. 二进制3、CPU可以直接访问的存储器是哪一个？A. 软盘B. 硬盘C. 内存D. 光盘4、在计算机网络中，以下哪项不是TCP/IP模型的层次结构之一？A. 网络接口层B. 网络层C. 应用层D. 物理层5、以下哪个算法是用于查找非平衡二叉搜索树中某个特定节点的最坏情况时间复杂度？A. 二分查找B. 中序遍历C. 平衡二叉搜索树查找D. 二叉树遍历6、以下哪个语言是用于实现编译原理的？A. JavaB. C++C. PythonD. Haskell7、在计算机系统中，地址总线的宽度决定了CPU可以直接寻址的内存空间大小。
如果某计算机系统的地址总线宽度为32位，则该CPU的最大直接寻址空间为：A. 4GBB. 8GBC. 16GBD. 32GB8、在数据结构中，队列是一种特殊的线性表，其特点是先进先出（FIFO）。
若在一个初始为空的队列中按照顺序插入元素A、B、C、D，然后执行两次删除操作，再插入元素E、F，接着再次执行两次删除操作，此时队列的队首元素是：A. AB. BC. CD. F9、在关系数据库中，两个表之间的连接是一种生成新表的操作，它将第一个表中的行与第二个表中的行匹配。
如果连接操作没有找到匹配项，则返回NULL。
假设我们有两个表：Table1(A, B)，Table2(C, D)，其中A与C是连接字段。
计算机导论考研题库计算机导论作为一门基础课程，对于考研的学生来说，掌握其核心概念和原理是非常重要的。
以下是一些计算机导论的考研题库内容，供参考：一、选择题1. 计算机科学的基础是______。
A. 硬件B. 软件C. 算法D. 数据结构2. 冯·诺依曼计算机体系结构中，CPU的主要功能是______。
A. 存储数据B. 处理数据C. 显示数据D. 传输数据3. 在计算机系统中，操作系统的主要作用是______。
A. 管理硬件资源B. 执行程序C. 存储数据D. 网络通信4. 数据库管理系统（DBMS）的基本功能不包括______。
A. 数据定义B. 数据存储C. 数据加密D. 数据恢复5. 计算机网络的拓扑结构中，不包括以下哪种类型？A. 星型B. 总线型C. 环形D. 树型二、简答题1. 请简述计算机硬件的基本组成，并说明各部分的功能。
2. 解释什么是程序，并描述程序的生命周期。
3. 什么是操作系统？请列出操作系统的五大基本功能。
4. 描述数据库管理系统的主要特点及其在现代信息系统中的作用。
5. 什么是网络协议？请举例说明网络协议在网络通信中的重要性。
三、论述题1. 论述计算机科学与信息技术的区别和联系。
2. 分析计算机病毒的特点及其对计算机系统可能造成的危害，并提出预防措施。
3. 论述云计算的概念、优势以及在现代企业中的应用。
4. 描述大数据时代下，数据挖掘技术的重要性和应用场景。
5. 论述人工智能的发展历程、当前挑战以及未来发展趋势。
请注意，以上题目仅为示例，实际考研题库内容可能会有所不同。
考生应根据具体考试大纲和教材内容进行复习准备。
希望这些题目能够帮助你更好地理解和掌握计算机导论的相关知识。
计算理论习题答案计算理论，也称为理论计算机科学，是研究算法和计算过程的数学理论基础的学科。
以下是一些计算理论习题的答案示例：1. 确定性图灵机（Deterministic Turing Machine, DTM）：- 习题：证明一个确定性图灵机可以模拟任何其他确定性图灵机。
- 答案：确定性图灵机可以读取输入，根据当前状态和读取到的符号，按照预定的转移规则移动磁带头并改变状态。
要模拟另一台确定性图灵机，只需要将被模拟机的状态转移表编码为模拟机的转移规则即可。
2. 非确定性图灵机（Nondeterministic Turing Machine, NTM）：- 习题：证明非确定性图灵机比确定性图灵机更强大。
- 答案：非确定性图灵机可以在多个可能的转移中选择，这使得它能够解决一些确定性图灵机无法解决的问题，例如哈密顿回路问题。
此外，任何确定性图灵机都可以被一个非确定性图灵机模拟，但反之则不成立。
3. 可计算性（Computability）：- 习题：证明某个特定的函数是可计算的。
- 答案：要证明一个函数是可计算的，需要展示一个算法或图灵机，它对于该函数的任何输入都能在有限步骤内给出输出。
例如，一个简单的加法函数f(x, y) = x + y是可计算的，因为它可以通过迭代或递归来实现。
4. 不可解问题（Undecidable Problems）：- 习题：解释停机问题（Halting Problem）为什么是不可解的。
- 答案：停机问题是不可解的，因为它涉及到预测一个图灵机是否会在有限步骤内停止。
如果存在一个算法能够解决停机问题，那么我们可以构造一个悖论，即一个图灵机可以模拟自身并决定自己是否会停止，这会导致自指的悖论。
5. 复杂性类（Complexity Classes）：- 习题：区分P类问题和NP类问题。
- 答案：P类问题是指可以在多项式时间内解决的问题，而NP类问题是指可以在多项式时间内验证一个解的问题。
东华大学2017~2018学年第一学期研究生期末考试试题考试学院：计算机考试专业：计算机科学与技术考试课程名称：计算理论导引与算法复杂性一、单项选择题（每空2分，本题共20分）1.关于集合S中的元素x，（）的说法是正确的。
A、x⊆SB、x可能是一个集合C、x在S中的顺序不能改变D、（x,x）∉S⨯S2.关于函数f，（）的说法是正确的。
A、f的值域一定是可数的B、f的定义域和值域的交集一定是空集C、f的值域不可能为{TRUE,FALSE}D、f的定义域可以是元组的集合3.关于正则语言R，（）的说法是正确的。
A、R是上下文无关的B、R是不能用正则表达式来描述的C、R是可以违反泵引理的D、R是图灵可识别但不可判定的4.关于乔姆斯基范式，（）的说法是错误的。
A、规则的右部可以是变量与终结符构成的串B、左部是起始变量的规则，其右部可以是εC、任意一个上下文无关文法都可以转化为乔姆斯基范式形式D、终结符一定单独出现在规则的右部5.关于下推自动机PDA，（）的说法是正确的。
A、PDA可以识别上下文无关语言B、PDA是DFA的一种特例C、PDA识别的语言NFA也能识别D、PDA的存储容量与GNFA相同6.关于图灵机M，（）的说法是正确的。
A、M一定是可停机的B、M识别的语言一定是可判定的C、M可以不识别任何语言D、M的存储容量比PDA大7.关于图灵不可识别语言L，（）的说法是错误的。
A、没有图灵机可识别LB、没有PDA可识别LC、L不能用正则表达式来描述D、目前L是否存在还是个未解之谜8.关于图灵不可判定语言L，（）的说法是错误的。
A、如果L是图灵可识别，那么，L一定是图灵不可识别的B、L一定是图灵可识别的C、如果L是图灵不可识别的，那么，L有可能是图灵可识别的D、如果L是图灵不可识别的，那么，L有可能是图灵不可识别的9.关于属于NP类的语言L，（）的说法是正确的。
A、L有可能属于P类B、L不能多项式时间规约到某个NP-complete语言C、如果NP类中所有语言都能多项式时间规约到L，那么，L是NP-hardD、L不可能是NP-complete10．关于PSPACE-hard语言L，（）的说法是正确的。
计算理论复习题1、 什么是图灵机，图灵机的构造技术以及三种描述方式是什么？(1)图灵机：一个图灵机是一个7元组（Q ，∑，，Γ，δ，0q ，accept q ，reject q ），其中,,Q ∑Γ都是有穷集合，并且○1Q 是状态集；○2∑是输入字母表，不包括特殊空白符号︼；○3 Γ是字母表，其中：︼∈Γ∑⊆Γ，；○4:{,}Q Q L R δ⨯Γ→⨯Γ⨯；○50q Q ∈是起始状态；○6accept q Q ∈是接受状态；○7reject q Q ∈是拒绝状态，且reject accept q q ≠。
(2)构造技术：○1有限控制器的存储构造TM ，检查第一个输入是不是出现在输入的其他地方；○2多道；○3查询符号（打标记）；○4移动：如把一个字符串整体后移; ○5调用子程序。
(3)描述方式：○1形式描述，即详尽地写出图灵机的状态、转移函数等，这是最低、最详细程度的描述；○2实现描述,这种方法使用日常语言来描述图灵机的运行，如怎么移动读写头，怎么在带上存储数据等，没有给出 状态和转移函数的细节；○3高水平描述，它也是使用日常语言来描述算法，但忽略了实现的模型，不再需要提及机器是怎么管理它的带子或读写头。
2、什么是图灵机的格局，图灵可识别，图灵可判定？(1)图灵机计算过程中，当前状态、当前带内容和读写头当前位置组合在一起，称为图灵机的格局，也即是瞬间状态。
(2)如果一个语言能被某一图灵机识别，则称该语言是图灵可识别的。
(3) 如果一个语言能被某一图灵机判定，则称它是图灵可判定的。
3、什么是多带图灵机，非确定型图灵机，枚举器，递归可枚举语言？(1)多带图灵机很像普通图灵机，只是有多个带子，每个带子都有自己的读写头，用于读和写。
开始时，输入出现在第一个带子上，其它的带子都是空白。
转移函数改为允许同时进行读、写和移动读写头，其形式为：δ：Q ⨯Γk →Q ⨯Γk ⨯},{R L k 此处k 是带子的个数。
研究生考试考研计算机学科专业基础(408)复习试卷(答案在后面)一、单项选择题（本大题有40小题，每小题2分，共80分）1、在计算机系统中，下列哪种存储器是用于存放机器指令的？A、只读存储器（ROM）B、随机存取存储器（RAM）C、光盘存储器D、硬盘存储器2、以下哪种编程语言被广泛用于开发操作系统？A、C语言B、JavaC、PythonD、Ruby3、在计算机网络中，以下哪个协议负责处理不同网络之间的数据交换？A、HTTP协议B、FTP协议C、SMTP协议D、TCP/IP协议4、下列关于数据结构中栈和队列的描述，不正确的是：A. 栈是一种后进先出（LIFO）的数据结构B. 队列是一种先进先出（FIFO）的数据结构C. 栈和队列都是线性表D. 栈可以采用链式存储结构，队列只能采用顺序存储结构5、以下关于哈希表的说法，正确的是：A. 哈希表可以解决所有数据结构的问题B. 哈希表的查找效率与哈希函数的选择无关C. 哈希表是一种通过哈希函数将数据元素映射到表中的数据结构D. 哈希表在发生哈希冲突时，一定需要使用链表来解决6、以下关于图数据结构的描述，不正确的是：A. 图可以表示任意复杂的关系B. 图的顶点可以是任何数据类型C. 图的边可以是单向或双向的D. 无向图和有向图的顶点数必须相同7、下列关于C++中构造函数和析构函数的说法，错误的是：A、构造函数在对象被创建时自动调用B、析构函数在对象被销毁时自动调用C、构造函数和析构函数可以有参数D、构造函数和析构函数的名字与类名相同8、在Java中，以下哪个关键字用来声明一个抽象类？A、publicB、abstractC、finalD、class9、以下关于数据库事务的ACID特性，哪个描述是错误的？A、原子性（Atomicity）确保事务中所有操作要么全部完成，要么全部不做B、一致性（Consistency）确保事务执行结果使得数据库从一个一致性状态转移到另一个一致性状态C、隔离性（Isolation）确保事务在并发执行时不会相互干扰D、持久性（Durability）确保事务一旦提交，其所做的更改将永久保存到数据库中10、在计算机网络中，以下哪个协议主要用于实现互联网中的电子邮件服务？A. HTTPB. FTPC. SMTPD. DNS11、在计算机组成原理中，以下哪个寄存器通常用于存储CPU的当前指令地址？A. 程序计数器（PC）B. 数据寄存器（DR）C. 累加器（ACC）D. 指令寄存器（IR）12、在操作系统原理中，以下哪个概念描述了进程在执行过程中可能遇到的三种基本状态？A. 进程调度B. 进程同步C. 进程状态D. 进程通信13、在计算机系统中，下列哪种设备属于I/O设备？A. 中央处理器（CPU）B. 存储器C. 硬盘D. 显卡14、下面哪种技术可以实现多级缓存一致性？A. 线性一致性模型B. 强一致性模型C. 松散一致性模型D. 缓存一致性协议15、以下哪个算法的时间复杂度是O(nlogn)？A. 冒泡排序B. 选择排序C. 快速排序D. 插入排序16、在C++中，以下哪个关键字用于声明一个指向常量的指针？A. constB. &constC. const*D. &*17、在Java中，下列哪个关键字用于声明一个接口？A. interfaceB. classC. extendsD. implements18、以下哪种数据结构可以实现动态数组的功能？A. 链表B. 栈C. 队列D. 动态数组19、在计算机网络中，以下哪个协议属于传输层协议？A. HTTPB. FTPC. SMTPD. TCP 20、以下哪个算法属于动态规划算法？A. 冒泡排序B. 快速排序C. 深度优先搜索D. 最长公共子序列21、在C++中，以下哪个关键字用于声明一个类的私有成员？A. publicB. protectedC. privateD. static22、以下哪种编程语言是面向对象编程语言？A. JavaB. CC. PythonD. JavaScript23、以下哪种数据结构是用于解决排序问题的？A. 队列B. 栈C. 树D. 散列表24、在计算机网络中，以下哪个协议用于传输文件？A. HTTPB. FTPC. SMTPD. DNS25、以下哪个操作系统不是基于分时多任务技术的？A. WindowsB. LinuxC. macOS26、在计算机网络中，以下哪个协议负责传输层的可靠性？A. IPB. TCPC. UDPD. HTTP27、在数据库设计中，以下哪个范式描述了“每个非主属性只依赖于主属性”？A. 第一范式（1NF）B. 第二范式（2NF）C. 第三范式（3NF）D. 第四范式（4NF）28、在C语言中，以下哪个关键字表示静态存储期的变量？A. staticB. externC. autoD. register29、以下哪个算法的时间复杂度是O(nlogn)？A. 快速排序B. 冒泡排序C. 选择排序D. 插入排序 30、在计算机网络中，以下哪个协议负责将数据包从源主机发送到目的主机？B. UDPC. IPD. HTTP31、以下关于C++中的构造函数的描述，错误的是：A. 构造函数是类的一个特殊成员函数，用于初始化对象B. 构造函数的函数名与类名相同C. 构造函数可以重载D. 构造函数不能有返回类型，即使是void也不可以32、在Java中，下列关于继承的说法，正确的是：A. 子类可以访问父类的所有成员变量和方法B. 子类可以访问父类中声明的私有成员变量和方法C. 子类可以修改父类中声明的私有成员变量和方法D. 子类可以重写父类中声明的私有成员变量和方法33、以下关于Python中列表（list）的说法，正确的是：A. 列表中的元素类型可以不同B. 列表中的元素类型必须相同C. 列表是不可变的，不能修改D. 列表是可变的，可以添加、删除和修改元素34、关于C++中的“引用”，以下说法错误的是：A. 引用是另一个变量的别名，对引用的操作等同于对原变量的操作。
计算机考研复试题库及答案一、操作系统1. 下面关于进程和线程的描述中，错误的是：答案：进程是操作系统分派资源的基本单位，线程是进程分派资源的基本单位。
2. 在Windows操作系统中，以下哪个命令用于查看当前正在运行的进程？答案：tasklist3. 下面哪条命令是Linux中用于创建新目录的？答案：mkdir二、数据结构与算法1. 下列选项中，时间复杂度最低的是：A. O(1)B. O(n)C. O(logn)D. O(nlogn)答案：A. O(1)2. 在一个有序数组中搜索一个特定的值，选择使用二分查找算法的时间复杂度是？答案：O(logn)3. 在以下排序算法中，哪个具有最坏情况时间复杂度为O(n^2)？A. 快速排序B. 归并排序C. 插入排序D. 堆排序答案：C. 插入排序三、计算机网络1. 下列关于HTTP和HTTPS协议的说法，哪个是正确的？答案：HTTPS是HTTP加密传输协议，通过SSL/TLS加密网络通信。
2. IP地址的分类中，192.168.0.1属于以下哪个分类？答案：私有IP地址3. HTTP协议是无状态的，这意味着服务器不会在多次请求之间保留任何信息。
要实现状态管理，HTTP协议使用以下哪种机制？答案：Cookie四、数据库1. SQL语句用于从关系数据库中选择数据的是？答案：SELECT2. 下面哪种数据库模型不属于非关系型数据库？A. 关系型模型B. 文档数据库模型C. 键值对模型D. 列族模型答案：A. 关系型模型3. 下面哪个SQL语句错误？A. SELECT * FROM students WHERE age>=18 AND age<=22B. SELECT * FROM students WHERE name LIKE '%Li%'C. SELECT * FROM students WHERE age BETWEEN 18 AND 22D. SELECT * FROM students WHERE name='Li' OR 'Wang'答案：D. SELECT * FROM students WHERE name='Li' OR 'Wang'五、计算机组成原理1. 下面哪个存储器属于易失性存储器？答案：DRAM2. 在计算机CPU中，下面哪个部件用于存储指令执行过程中的中间结果？答案：寄存器3. 下面对于计算机处理器的描述中，错误的是？答案：处理器的时钟频率越高，性能越低。
1、请你从形式定义、计算过程和对应的语言特点关系等诸方面综合比较DFA、PDA和图灵机
2、对于简单文法（正则语言、上下文无关语言），能够根据其产生式写出其语言
3、正则语言泵引理和上下文无关语言泵引理的理解、相互比较和应用
4、最简DFA、最简PDA的概念；DFA和PDA的简化过程；（带ε和不带ε的）NFA化简成最简DFA的过程
5、图灵机的Golder编码和通用图灵机的编码
6、上下文无关文法的乔姆斯基范式
7、DFA的计算过程
8、上下文无关文法的推导过程以及其歧义相关概念及分析
9、关于四类乔姆斯基语言及其对应的自动机类型特点分析
10、四类乔姆斯基语言的各种运算类型并形式化表示
11、关于CFG和DFA的若干判定问题
12、关于若干渐进符号：同阶渐进符号Θ、大O、小O和大Ω符号的含义和用法
13、请从NP类问题、P类问题、确定型单带TM、确定型多带TM、非确定型TM等角度综述
时间复杂性规律
相关例题：
1、请你综合比较DFA、PDA和图灵机
2、请写出下列表达式生成的正则语言
1）设有文法G=(V,T,P,S)，其中V={S,A,B}，T={a,b}，P：S→aB；S→bA；A→bAA；A →a；A→aS；B→b；B→bS；B→aBB
请写出L(G)=
2）设一个有穷自动机M=(Q,∑,δ,q0,F)，其中Q={q0,q1,q2,q3)，∑={0,1}, F={q0}，δ如下：
δ(q0,0)=q2, δ(q0,1)=q1, δ(q1,0)=q3, δ(q1,1)=q0
δ(q2,0)=q0, δ(q2,1)=q3, δ(q3,0)=q1, δ(q3,1)=q2
请写出L(M)=
3）设有文法G=({S,A},{a,b,c,d};R,S)，其中R：S→aSd|aAd，
A→bAc|bc
请写出L(G)=
3、用泵引理证明下列论点
1）A1={a n b n c n|n≥0}不是正则语言
2）D={ww|w∈{0，1}*}不是上下文无关语言
4、把下面状态转换图代表的DFA变化成最简DFA
5、设有图灵机M=({q1,q2,q3},{0,1},{0,1,B},δ,q1,B,{q2})，其中转移函数δ为δ(q1,1)=
(q3,0,R)；δ(q3,0)=(q1,1,R)；δ(q3,1)= (q2,0,R)；δ(q3,B)=(q3,1,L)，试写出其标准编码
6、将文法G转换成乔姆斯基范式，其中G=({S,A},{a,b,c},R,S)，R：S→aS|A, A→bA|c
7、试描述将一台带ε的NFA转换成等价的DFA的过程
8、请你从形式定义、计算过程和对应的语言特点关系等诸方面综合比较DFA、PDA和图灵机
9、对于上下文无关文法G=(V,T,P,S)，其中V={S,A,B}，T={a,b}，P：S→aB|bA；A→a|aS|bAA；
B→b|bS|aBB，则
1）请写出L(G)=
2）给出终极符串x=aaabbabbba的最左推导、最右推导和推导树
3）这个文法是否有歧义，如果有歧义，能否给出等价的非歧义文法
10、设有图灵机M=({q1,q2,q3},{0,1},{0,1,B},δ,q1,B,{q2})，其中转移函数δ为
δ(q1,1)=(q3,0,R)；δ(q3,0)=(q1,1,R)；δ(q3,1)=(q2,0,R)；δ(q3,B)=(q3,1,L)，试写出其标准编码
11、将文法G=({S,A,B},{a,b},R,S)，R：S→bA|aB，A→bAA|aS|a，B→aBB|bS|b转换成乔
姆斯基范式
12、用泵引理证明下列论点
1）A={n
a2|n≥0}不是正则语言
2）B={ab，aabb，…，a k b k，…}={a k b k|k≥1}不是正则语言
3）C={a i b j c i d j|i，j≥1}不是上下文无关语言
13、请列出你所知道的有关四类乔姆斯基语言的运算类型并形式化表示之
14、请写出下列表达式生成的正则语言
1）设一个有穷自动机M=(Q,∑,δ,q0,F)，其中Q={q0,q1,q2,q3)，∑={0,1}, F={q0}，δ如下：δ(q0,0)=q2, δ(q0,1)=q1, δ(q1,0)=q3, δ(q1,1)=q0, δ(q2,0)=q0, δ(q2,1)=q3, δ(q3,0)=q1, δ(q3,1)=q2。
请写出L(M)=
2）设有文法G=({S,A},{a,b,c,d};R,S)，其中R：S→aSd|aAd，
A→bAc|bc。
请写出L(G)=
15、关于泵引理
1）请从内容描述和实质蕴涵两个角度描述并比较有关正则语言和上下文无关语言的两个泵引理
2）证明语言L={a i b j c i d j|i,j>0}不是上下文无关语言
16、设有图灵机M=({q1,q2,q3},{0,1},{0,1,B},δ,q1,B,{q2})，其中转移函数δ为
δ(q1,1)=(q3,0,R)；δ(q3,0)=(q1,1,R)；δ(q3,1)=(q2,0,R)；δ(q3,B)= (q3,1,L)，试写出其标准编码
17、关于判定问题
1）下面是CFG派生问题A CFG={<G,ω>|G是CFG，ω是串，G派生ω}图灵机高层描述，请用类C语言写出其算法
2）设有一个上下文无关文法G，它的产生式集为S→AB|BC；A→BA|a；B→CC|b；C→AB|c，和一个终极符串x=baaba，用你给出的算法判定是否x∈L(G)
18、关于同阶渐进符号用法Θ
1）f(n)和g(n)是两通常数论函数，请给出其同阶渐进的定义。
2）请用精确的数学语言证明5n2＋8n＋1＝Θ(n2)
对每一类语言可以提出的判定问题
空集问题：对任意给定的一个语言L的表示，判定L是否为空集
全集问题：对任意给定的字母表Σ上的一个语言L的表示，判定L=Σ*
有限和无限问题：对任意给定的一个语言L的表示，判定L是有限集或无限集
成员问题：对任意给定的字母表Σ上的一个语言L和任意一个串x∈Σ*，判定是否有x∈L 相等性问题：对任意给定的两个语言L1和L2，判定是否有L1=L2
子集问题：对任意给定的两个语言L1和L2，判定是否有L1⊆L2
CFG派生串问题的CYK算法
例题：设有一个上下文无关文法G，它的产生式集为S→AB|BC；A→BA|a；B→CC|b；C→AB|c，和一个终极符串x=baaba，要用CYK算法判定是否x∈L(G)
由算法的第一步，V11={E|E→b}={B}，V21={E|E→a}={A，C}，V21=V51={A，C}， V21=V51={B} 由算法的第二步，可以求Vi2，i=1，…，5-2+1，例如V12={E|E→FH，F∈V11，H∈V21}={E|E →BA，或E→BC}={S，A}
其他依次类推，V15={S，A，C}，由于S∈V15，则X∈L(G)
乔姆斯基语言体系：
正规语言是确定上下文无关语言的真子类
确定上下文无关语言类是上下文无关语言的真子类
上下文无关语言类是上下文有关语言类的真子类
上下文有关语言类是递归语言的真子类
递归语言类是递归可枚举语言的真子类
对于语言，可以定义多种运算
语言集合所定义的各种运算：并,补,交,差等
语言字符串所定义的各种运算：求逆、求前缀、求后缀、连接等
语言字母表与语言字母表之间的映射：替换、同态、逆同态等。
