下载文档原格式
2.2 a. 利用语言A={a m b n c n | m,n ≥0}和A={a n b n c m | m,n ≥0}以及例3.20，证明上下文无关语言在交的运算下不封闭。
b. 利用(a)和DeMorgan 律(定理1.10)，证明上下文无关语言在补运算下不封闭。
证明：a.先说明A,B 均为上下文无关文法，对A 构造CFG C 1S →aS|T|ε T →bTc|ε对B,构造CFG C 2S →Sc|R|ε R →aRb由此知 A,B 均为上下文无关语言。
但是由例3.20, A ∩B={a nb nc n|n ≥0}不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。
b.用反证法。
假设CFL 在补运算下封闭，则对于(a)中上下文无关语言A,B ，A ,B也为CFL ，且CFL 对并运算封闭，所以B A ⋃也为CFL ，进而知道BA ⋃为CFL ，由DeMorgan 定律B A ⋃＝A ∩B ，由此A ∩B 是CFL,这与(a)的结论矛盾，所以CFL 对补运算不封闭。
2.4和2.5 给出产生下述语言的上下文无关文法和PDA ，其中字母表∑={0,1}。
a. {w | w 至少含有3个1}S →A1A1A1A A →0A|1A|ε0, ε→εb. {w | w 以相同的符号开始和结束}S →0A0|1A1 A →0A|1A|εc. {w | w 的长度为奇数}S →0A|1A A →0B|1B|ε B →0A|1Ad. {w | w 的长度为奇数且正中间的符号为0}S →0S0|1S1|0S1|1S0|0e. {w | w 中1比0多}S →A1A0,ε→ε 0,ε→ε 1,ε→ε 0,ε→ε 0,ε→0 0,0→εA →0A1|1A0|1A|AA|εf. {w | w=w R }S →0S0|1S1|1|0g. 空集S →S2.6 给出产生下述语言的上下文无关文法：a ．字母表{a,b}上a 的个数是b 的个数的两倍的所有字符串组成的集合。
![计算理论导引习题答案[第2版]CHAP5new](https://img.taocdn.com/s1/m/14a23d6565ce0508773213a8.png)
5.1 证明EQ CFG 是不可判定的。
解：只须证明ALL CFG ≤m EQ CFG 即可。
构造CFG G 1，使L(G 1)=∑*。
设计从ALL CFG 到EQ CFG 的归约函数如下： F=“对于输入＜G ＞，其中G 是CFG ：1）输出＜G ,G 1＞。
”若＜G ＞ALL CFG ，则<G ,G 1>EQ CFG 。
若＜G ＞ALL CFG ，则<G , G 1>EQ CFG 。
F 将ALL CFG 归约到EQ CFG 即ALL CFG ≤m EQ CFG∵ALL CFG 是不可判定的，∴EQ CFG 是不可判定的。
5.2证明EQ CFG 是补图灵可识别的。
证明：注意到A CFG ={<G,w>|G 是能派生串w 的CFG}是可判定的。
构造如下TM ： F=“输入<G ,H>，其中G ,H 是CFG ，1) 对于字符串S 1, S 2,，重复如下步骤。
2) 检测S i 是否可以由G 和H 派生。
3) 若G 和H 中有一个能派生w ，而另一个不能，则接受。
”F 识别EQ CFG 的补。
5.3 略。
5.4 如果A m B 且B 是正则语言，这是否蕴涵着A 也是正则语言？为什么？ 解：否。
例如：对非正则语言A={0n 1n |n 0}和正则语言B={0}，可以构造一个可计算函数f 使得：f(w)=⎩⎨⎧≠=n n nn 10w 1,10w 0, 于是w A f(w)B,故A m B 。
5.5 证明A TM 不可映射规约到E TM 。
证明：反证法假设A TM m E TM ， 则有TM m TM E A ≤。
而A TM 的补不是图灵可识别的，从而可知E TM 的补也不是图灵可识别的。
下面构造一个识别E TM 的补的图灵机S ：S=“输入<M>，M 是TM,1) 对i=1,2,…重复下一步。
2) 对S 1,S 2,…,S i 模拟M 运行i 步，若有接受，则接受。
计算机考博试题计算理论及答案计算理论字母表：⼀个有穷的符号集合。
字母表上的字符串是该字母表中的符号的有穷序列。
⼀个字符串的长度是它作为序列的长度。
连接反转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），另外，还有⼀个程序对这个盒⼦进⾏控制。
计算理论习题答案CHAP2new2.2 a. 利⽤语⾔A={a m b n c n | m,n ≥0}和A={a n b n c m | m,n ≥0}以及例3.20，证明上下⽂⽆关语⾔在交的运算下不封闭。
b. 利⽤(a)和DeMorgan 律(定理1.10)，证明上下⽂⽆关语⾔在补运算下不封闭。
证明：a.先说明A,B 均为上下⽂⽆关⽂法，对A 构造CFG C 1S →aS|T|ε T →bTc|ε对B,构造CFG C 2S →Sc|R|ε R →aRb由此知 A,B 均为上下⽂⽆关语⾔。
但是由例3.20, A ∩B={a nb nc n|n ≥0}不是上下⽂⽆关语⾔，所以上下⽂⽆关语⾔在交的运算下不封闭。
b.⽤反证法。
假设CFL 在补运算下封闭，则对于(a)中上下⽂⽆关语⾔A,B ，A ,B也为CFL ，且CFL 对并运算封闭，所以B A ?也为CFL ，进⽽知道BA ?为CFL ，由DeMorgan 定律B A ?＝A ∩B ，由此A ∩B 是CFL,这与(a)的结论⽭盾，所以CFL 对补运算不封闭。
2.4和2.5 给出产⽣下述语⾔的上下⽂⽆关⽂法和PDA ，其中字母表∑={0,1}。
a. {w | w ⾄少含有3个1}S →A1A1A1A A →0A|1A|ε0, ε→εb. {w | w 以相同的符号开始和结束}S →0A0|1A1 A →0A|1A|εc. {w | w 的长度为奇数}S →0A|1A A →0B|1B|ε B →0A|1Ad. {w | w 的长度为奇数且正中间的符号为0}S →0S0|1S1|0S1|1S0|0e. {w | w 中1⽐0多}S →A1A0,ε→ε 0,ε→ε 1,ε→ε 0,ε→ε 0,ε→0 0,0→εA →0A1|1A0|1A|AA|εf. {w | w=w R }S →0S0|1S1|1|0g. 空集S →S2.6 给出产⽣下述语⾔的上下⽂⽆关⽂法：a ．字母表{a,b}上a 的个数是b 的个数的两倍的所有字符串组成的集合。
一、证明：设M是一台识别语言B的DFA，交换M的接受状态与非接受状态得到一台新的DFA，则这台新DFA识别B的补集。
因而，正则语言类在补运算下封闭。
(8分)参考答案：设M’是一台将DFA M的接受态与非接受态交换后的DFA，接下来证明M识别B语言，则M’识别B的补集：假定M’识别x，则对于x 在M’上运行将结束于M’的一个接受态，因为M和M’交换了接受态与非接受态，因此对于x运行于M，将会结束于一个非接受态，所以x∈/B。
类似地，如果x不被M’接受，则它一定被M接受。
故M’恰好接受所有不被M接受的那些串，因此M’识别B的补集。
既然B是任意的正则语言，且我们已构造出一台自动机识别它的补集，它表明任何正则语言的补也是正则的。
因此，正则语言类在补运算下封闭。
二、令∑＝｛0，1，＋，＝｝和ADD＝｛x=y+z | x，y，z是二制整数，且x是y与z的和｝，证明ADD不是正则的。
(8分)参考答案：假定ADD是正则的。
让P作为泵引理中的泵长度，选择S的串形式为1P＝0P＋1P作为ADD的一个成员。
因为S有长度大于P，由泵引理保证它能分割成形如：S＝xyz的三部分，满足泵引理的条件。
泵引理的第三个条件有｜xy｜≤P，《它表明对于K≥1，y就是1K。
这是xy2z是串1P＋K＝OP＋1P，而它不是ADD的成员，由泵引理导出矛盾，因此ADD不是正则的。
三、请将下述CFG转换成等价的乔姆斯基范式文法。
(8分)A→BAB｜B｜εB→00｜ε参考答案：S0→AB｜CC｜BA｜BD｜BB｜εA→AB｜CC｜BA｜BD｜BBB→CCC→0D→AB四、请用泵引理证明语言A＝｛0n＃02n＃03n | n≥0 ｝不是上下文无关的。
(8分)参考答案：由泵引理，让P作为泵长度，s=0p＃02p＃03p ，接下来证明s=uvxyz不能进行泵抽取。
v和y都不能包含＃，否则，xv2wy2z将超过2个＃s ，因此，如果我们按＃’s将s分成三段如：0p，02p，03p，至少有一段不包含v或y。
计算机复习计算理论计算机是现代社会不可或缺的重要工具之一，而计算理论正是计算机科学的核心内容之一。
本文将对计算机复习计算理论进行全面的介绍，包括题库类型、答案和解析，并以清晰的排版和流畅的语句来呈现。
以下是相关内容的详细讨论。
第一章：数据结构与算法1. 题目类型：多选题题目：以下哪种数据结构适合快速查找一个元素？A. 数组B. 链表C. 堆D. 哈希表答案：D解析：哈希表能够通过散列函数将元素映射到一个固定的位置，因此可以快速查找一个元素。
2. 题目类型：填空题题目：在计算机科学中，时间复杂度用大O表示，表示算法的运行时间与输入规模的关系，常用的时间复杂度包括O(1)、O(log n)、O(n)等。
请将以下时间复杂度按照增长顺序从小到大进行排序。
答案：O(1) < O(log n) < O(n)解析：O(1)表示常数时间复杂度，O(log n)表示对数时间复杂度，O(n)表示线性时间复杂度，根据增长趋势，可得排序结果。
第二章：计算机网络1. 题目类型：单选题题目：在计算机网络中，下列哪个协议用于将域名解析为IP地址？A. HTTPB. FTPC. DNSD. TCP答案：C解析：DNS（Domain Name System）是用于将域名解析为IP地址的协议。
2. 题目类型：判断题题目：TCP是一种面向无连接的传输层协议。
答案：错误解析：TCP（Transmission Control Protocol）是一种面向连接的传输层协议，而非面向无连接的。
第三章：操作系统1. 题目类型：填空题题目：在现代操作系统中，内存管理的最小单位是________。
答案：字节（Byte）解析：现代操作系统中的内存管理以字节为最小单位进行。
2. 题目类型：多选题题目：以下哪个调度算法不考虑进程的优先级？A. 先来先服务（FCFS）B. 最短作业优先（SJF）C. 时间片轮转（RR）D. 最高响应比优先（HRRN）答案：A、B、C解析：先来先服务、最短作业优先和时间片轮转调度算法都不考虑进程的优先级。
计算理论答案计算理论答案第一套BCACC CBCBB BBABC ACDAC1．下列叙述中，正确的是（）。
A)CPU能直接读取硬盘上的数据B)CPU能直接存取内存储器C)CPU由存储器、运算器和控制器组成D)CPU主要用来存储程序和数据2．1946年首台电子数字计算机ENIAC问世后，冯·诺依曼(Von Neumann)在研制EDVAC 计算机时，提出两个重要的改进，它们是（）。
A)引入CPU和内存储器的概念B)采用机器语言和十六进制C)采用二进制和存储程序控制的概念D)采用ASCII编码系统3．汇编语言是一种（）。
A)依赖于计算机的低级程序设计语言B)计算机能直接执行的程序设计语言C)独立于计算机的高级程序设计语言D)面向问题的程序设计语言4．假设某台式计算机的内存储器容量为128MB，硬盘容量为10GB。
硬盘的容量是内存容量的（）。
A)40倍B)60倍C)80倍D)100倍5．计算机的硬件主要包括：中央处理器(CPU)、存储器、输出设备和（）。
A)键盘B)鼠标C)输入设备D)显示器6．根据汉字国标GB2312－80的规定，二级次常用汉字个数是（）。
A)3000个B)7445个C)3008个D)3755个7．在一个非零无符号二进制整数之后添加一个0，则此数的值为原数的（）。
A)4倍B)2倍C)1/2倍D)1/4倍8．Pentium(奔腾)微机的字长是（）。
A)8位B)16位C)32位D)64位9．下列关于ASCII编码的叙述中，正确的是（）。
A)一个字符的标准ASCII码占一个字节，其最高二进制位总为1B)所有大写英文字母的ASCII码值都小于小写英文字母'a'的ASCII 码值C)所有大写英文字母的ASCII码值都大于小写英文字母'a'的ASCII 码值D)标准ASCII码表有256个不同的字符编码10．在CD光盘上标记有"CD－RW"字样，此标记表明这光盘（）。
8.1 证明对于任意函数f:N N，其中f(n)n，不论用单带TM模型还是用两带只读输入TM模型，所定义的空间复杂性类SPACE(f(n))总是相同的。
证明：为区别，记单带TM模型在f(n)空间内能判定的语言类为SPACE1(f(n)), 而记双带只读输入TM模型在f(n)空间内能判定的语言类为SPACE2(f(n))。
该题要证明的是SPACE1(f(n))＝SPACE2(f(n))。
首先SPACE1(f(n))SPACE2(f(n))。
这是因为设A SPACE1(f(n))，且设M设在f(n)空间内判定A的单带TM，如下构造双带TM只读输入TM N。
N=“对于输入串w：1)将w复制到工作带上。
2)在工作带上模拟M，直到停机。
3)若M接受，则接受；否则，拒绝。
”N在f(n)空间内运行，L(N)=L(M)=A，所以A SPACE2(f(n))。
首先SPACE2(f(n))SPACE1(f(n))。
设A SPACE2(f(n))，且N 为在f(n)空间内判定A的双带只读输入TM。
按照用单带TM模拟多带TM的常规方式构造M：M＝“对于输入串w：1)初始化工作带为＃w1’w2…w n#’.其中以’标记N的两个读写头。
2)模拟N运行直到停机。
每一步模拟，要两次扫描带子。
第一次扫描确定读写头下符号，第二次扫描根据N的转移函数完成改写和移动读写头的工作。
3)若N接受，则接受；否则，拒绝。
”L(M)=L(N)=A。
由于f(n)n，M的运行空间是f(n)+n+2＝O(f(n))。
8.3 考虑广义地理学游戏，其中起始节点就是又无源箭头指入的节点。
选手I有必胜策略吗？选手II呢？给出理由。
1 2 34 5 6I II I II I Winner2 3 6 I4 5 6 II由表上来看选手II有必胜策略I2II4(不能选3)I5II6(不能选2)I。
8.4 证明PSPACE在并、补和星号运算下封闭。
证明：(1) 并：对任意L1, L2PSPACE，设有n a空间图灵机M1和n b空间图灵机M2判定它们，且c=max{a,b}。
计算理论答案汇总第一章练习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的形式描述.M1=(Q1,Σ,δ1,q1,F1) 其中 1）Q1={q1,q2,q3,}; 2）Σ={a,b}; 3）δ1为：a b q1 q2 q1 q2 q3 q3 q3 q2 q1 4）q1是起始状态 5）F1={q2}M2=(Q2,Σ,δ2,q2,F2) 其中 1）Q2={q1,q2,q3,q4}; 2）Σ={a,b}; 3）δ2为： a b q1 q1 q2 q2 q3 q4 q3 q2 q1 q4 q3 q4 3）q2是起始状态 4）F2={q1,q4} 1.3 DFA M的形式描述为 ( {q1，q2，q3，q4，q5}，{u,d},δ,q3，{q3}),其中δ在表2-3中给出。
试画出此机器的状态图。
d d d d u q1 q2 q3 d q4 q5 u u u u1.6 画出识别下述语言的DFA的状态图。
a){w | w从1开始以0结束}11 1 00 00,1b){w | w至少有3个1}0 0 0 0,1c) {w | w含有子串0101} 0,1 1 0 0 0 1 0 11d) {w | w的长度不小于3，且第三个符号为0}0,1 1 00,1 0,1 01 0,1e) {w | w从0开始且为奇长度，或从1开始且为偶长度} 0,10 0 或 0,1 0,1 0,1 0,1 1 10,1f) {w | w不含子串110} 0 1 0,11 1 00 5} g) {w | w的长度不超过0,10,1 0,1 0,1 0,1 0,1 0,1h){w | w是除11和111以外的任何字符}1 1 1 0 0 0 0,1i){w | w的奇位置均为1}10,1 0j) {w | w至少含有2个0，且至多含有1个1} 110 01 1 0,11 0 010 0k) {ε,0} 0 0,1 0,11l) {w | w含有偶数个0，或恰好两个1}1 1 110 0 0 0 0 0 0 0 1 1 1 1m) 空集 n) 除空串外的所有字符串 0,1 0,1 0,11.7 给出识别下述语言的NFA，且要求符合规定的状态数。
练习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个状态。
d. 语言｛0｝，2个状态。
e. 语言0*1*0*0，3个状态。
f. 语言{ε}，1个状态。
g. 语言0*，1个状态。
2.11证明每一台NFA 都能够转换成等价的只有一个接受状态的NFA 。
证明:设NFA M={Q ，Σ,δ,q 0,F}，F={r i1，……，r ik }.添加一个状态p 后，r i1，……，r ik 分别向p 引ε箭头，将r i1，……，r ik 变为非接受状态，p 变为接受状态。
又因为添加ε箭头不影响NFA 识别语言，所以命题成立。
2.14 a 证明：设M 是一台语言B 的DFA ，交换M 的接状态与非接受状态得到一台新的DFA ，则这台新的DFA 是识别B 的补集，因此，正则语言类受在补运算下封闭。
b 举例说明：设M 是一台识别语言B 的NFA ，交换M 的接受状态与非接受状态得到一台新的NFA ，这台新的NFA 不一定识别B 的补集。
NFA 识别的语言类在补集下封闭吗？解释你的回答。
解：a. M 是DFA, M 是{Q,∑,δ,q 0,F},令N={Q,∑,δ,q 0,Q-F},设ω=ω1ω2…ωn 是字母表上任意字符串，因为M 与N 均为DFA,所以必然存在Q 中状态序列r 0,r 1,…,r n ,使得：r 0=q 0, δ(r i , ωi+1)=r i+1, i=0,…,n-11)若r n ∈F 则ω∈B;2)若r n ∉F,则r n ∈Q-F,即N 接受ω，若ω∉B,所以N 接受B 的补集，即B 的补集正则。
所以，正则语言类在补运算下封闭。
b. 设B 为{0}。
NFA M ：可识别它。
依题对它作变换，得到N ：则N 识别的语言{ε}不是B 的子集。
所以交换M 的接受状态与非接受状态得到的新的NFA 不一定识别B 的补集。
但是由于NFA 识别的语言类与DFA 识别的语言类相同，即正则语言类。
由a 的证明，正则语言类在补运算封闭，可知，NFA 识别的语言类---正则语言类在补运算下封闭。
若NFA 识别语言A ，必有 等价的DFA 识别A,从而由a 知，可交换DFA 的接受与非接受状态构造识别A 的补集的DFA,则必有等价的NFA 识别A 的补集。
只是，该NFA 未必有原NFA 交换接受与非接受状态构造而成。
1.15 给出一个反例，说明下述构造不能证明定理2.24，即正则语言类在星号运算下封闭。
设N=（Q 1,Σ,δ1,q 1,F 1）识别A 1。
如下构造N=（Q 1,Σ,δ1,q 1,F 1）。
N 应该识别A 1*。
a. N 的状态集是N 1的状态集。
b. N 的起始状态是N 1的起始状态相同。
c. F=｛q 1｝∪F 1。
F 的接受状态是原来的接受状态加上它的起始状态。
d. 定义δ如下：对每一个q 属于Q 和每一个a 属于Σ。
⎩⎨⎧≠∈⋃≠∉=εδεδδa F q q a q a F q a q a q },{),( ),,(),(11111且若或若解：设N 1识别语言A={至少含有一个1}，其中输入字母表为{0，1}，可知A *={空串或至少含有一个1}。
N 1:N:所以如此构造的N 不一定识别A *.1.16 使用定理2.19中给出的构造，把下图中的两台非确定型有穷自动机转换成等价的确定型有穷自动机。
a)，b)，解：a), b)2.13 给出生成练习2.4中语言的正则表达式。
(注: 答案不唯一)a. {w | w 从1开始以0结束} 1Σ*0.b. {w | w 至少有3个1} Σ*1Σ*1Σ*1Σ*.c. {w | w 含有子串0101} Σ*0101Σ*.d. {w | w 的长度不小于3，且第三个符号为0} ΣΣ0Σ*.e. {w | w 从0开始且为奇长度，或从1开始且为偶长度} 0(ΣΣ)*⋃1Σ(ΣΣ)*.f. {w | w 不含子串110} (0⋃10) *1*.g. {w | w 的长度不超过5} ε⋃Σ⋃ΣΣ⋃ΣΣΣ⋃ΣΣΣΣ⋃ΣΣΣΣΣ.h. {w | w 是除11和111以外的任何字符} 0Σ*⋃10Σ*⋃110Σ*⋃111ΣΣ*.i. {w | w 的奇位置均为1} (1Σ)*( ε⋃1).j. {w | w 至少含有2个0，且至多含有1个1} 0*(00⋃010⋃001⋃100) 0*. k. {ε,0}. ε⋃0.l. {w | w 含有偶数个0，或恰好两个1} (1*01*0)*1*⋃0*10*10*.m. 空集. ∅.n. 除空串外的所有字符串ΣΣ*.a,b b1.19对下述每一个语言，给出4个字符串，2个是这个语言的成员，2个不是这个语言的成员。
这里假设字母表Σ={a,b}.a. a*b* 成员：ab，aab 非成员：aba，bab. a(ba)* 成员：ab，abab 非成员：abb，aac. a*⋃b*成员：aaa，bbb 非成员：ab，bad. (aaa)*成员：aaa，aaaaaa 非成员：a，aae.Σ*aΣ*bΣ*aΣ* 成员：aba，aaba 非成员：aa，abbf. aba⋃bab 成员：aba，bab 非成员：a，bg. (ε⋃a)b 成员：b，ab 非成员：a，bbh. (a⋃ba⋃bb) Σ*成员：a，bb 非成员：ε，b1.21 使用引理2.32中叙述的过程，把图2-38中的有穷自动机转换成正则表达式。
a),b),解: a) a*b(a⋃ba*b)*b) ε⋃(a⋃b)a*b[(aa⋃ab⋃b)a*b]*(a⋃ε).(注：答案不唯一)1.29利用泵引理证明下述语言不是正则的。
a. A1={0n1n2n| n≥0}。
证明：假设A1是正则的。
设p是泵引理给出的关于A1的泵长度。
令S=0p1p2p,∵S是A1的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。
根据条件3，y中只含0，xyyz中，0比1、2多，xyyz不是A1的成员。
违反泵引理的条件1，矛盾。
∴A1不是正则的。
b. A2={www | w∈{a,b}*}.证明：假设A2是正则的。
设p是泵引理给出的关于A2的泵长度。
令S=a p ba p ba p b,∵S是A2的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。
根据条件3，y中只含a，所以xyyz 中第一个a的个数将比后两个a的个数多，故xyyz不是A2的成员。
违反泵引理的条件1，矛盾。
∴A2不是正则的。
c. A3={a2n | n≥0}.(在这里，a2n表示一串2n个a .)a证明：假设A 3是正则的。
设p 是泵引理给出的关于A 3的泵长度。
令S= a 2p ，∵S 是A 2的一个成员且S 的长度大于p ，所以泵引理保证S 可被分成3段S=xyz 且满足泵引理的3个条件。
即对任意的i ≥0，xy i z 都应在A 3中，且xy i z 与xy i+1z 的长度都应是2的幂. 而且xy i+1z 的长度应是xy i z 的长度的2n 倍(n ≥1)。
于是可以选择足够大的i ，使得|xy i z|=2n >p. 但是|xy i+1z|-|xy i z|=|y|≤p. 即|xy i+1z|<2n+1, 矛盾。
∴A 3不是正则的。
1.30下面“证明”0*1*不是正则语言，指出这个“证明”中的错误。
(因为0*1*是正则的，所以一定错误。
) 采用反证法证明。
假设0*1*是正则的。
令P 是泵引定理给出的关于0*1*的泵长度。
取S 为字符串0p 1p 。
S 是0*1*的一个成员，但是例2.38已证明S 不能被抽取。
于是得到矛盾，所以0*1*不是正则的。
解：在例2.38中的语言是{0n 1n | n ≥0}，取S 为字符串0p 1p ，S 确实不能被抽取；但针对语言0*1*，S 是能被抽取的。
将S 分成三段S=xyz ，由泵引理的条件3，y 仅包含0，而xy i z 属于语言0*1*，即S 能被抽取，故题设中的“证明”不正确。
1.24有穷状态转换器(FST)是确定性有穷自动机的一种类型。
它的输出是一个字符串，而不仅仅是接受或拒绝。
图2—39是两台有穷状态状态转换器T 1和T 2的状态图。
T 1 T 2FST 的每一个转移用两个符号标记，一个指明该转移的输入符号，另一个指明输出符号。
两个符号之间用斜杠“/”把它们分开。
在T 1中，从q 1到q 2的转移有输入符号2和输出符号1。
某些转移可能有多对输入-输出，比如T 1中从q 1到它自身的转移。
FST 在对输入串w 计算时，从起始状态开始，一个接一个地取输入符号w 1⋯w n ，并且比照输入标记和符号序列w 1⋯w n =w 进行转移。
