第一章 1．比较数字计算机和模拟计算机的特点 解：模拟计算机的特点：数值由连续量来表示，运算过程是连续的；数字计算机的特点：数值由数字量（离散量）来表示，运算按位进行。两者主要区别见 P1 表 1.1 。 2．数字计算机如何分类？分类的依据是什么？ 解：分类：数字计算机分为专用计算机和通用计算机。通用计算机又分为巨型机、大型机、 中型机、小型机、微型机和单片机六类。分类依据：专用和通用是根据计算机的效率、速度、价格、运行的经济性和适应性来划分的。 通用机的分类依据主要是体积、简易性、功率损耗、性能指标、数据存储容量、 指令系统规模和机器价格等因素。 3．数字计算机有那些主要应用？（略） 4．冯 . 诺依曼型计算机的主要设计思想是什么？它包括哪些主要组成部分？ 解：冯 . 诺依曼型计算机的主要设计思想是：存储程序和程序控制。存储程序：将解题的程序（指令序列）存放到存储器中；程序控制：控制器顺序执行存储的程序，按指令功能控制全机协调地完成运算任务。 主要组成部分有：控制器、运算器、存储器、输入设备、输出设备。 5．什么是存储容量？什么是单元地址？什么是数据字？什么是指令字？ 解：存储容量：指存储器可以容纳的二进制信息的数量，通常用单位KB MB GB来度量，存储 容 量越大，表示计算机所能存储的信息量越多，反映了计算机存储空间的大小。单元地址：单元地址简称地址，在存储器中每个存储单元都有唯一的地址编号，称为单元地 址。 数据字：若某计算机字是运算操作的对象即代表要处理的数据，则称数据字。指令字：若某计算机字代表一条指令或指令的一部分，则称指令字。 6．什么是指令？什么是程序？ 解：指令：计算机所执行的每一个基本的操作。程序：解算某一问题的一串指令序列称为该问题的计算程序，简称程序。 7．指令和数据均存放在内存中，计算机如何区分它们是指令还是数据？ 解：一般来讲，在取指周期中从存储器读出的信息即指令信息；而在执行周期中从存储器中读出的信息即为数据信息。
第1章计算机系统概论 1. 什么是计算机系统、计算机硬件和计算机软件？硬件和软件哪个更重要？ 解： 计算机系统：由计算机硬件系统和软件系统组成的综合体。 计算机硬件：指计算机中的电子线路和物理装置。 计算机软件：计算机运行所需的程序及相关资料。 硬件和软件在计算机系统中相互依存，缺一不可，因此同样重要。 2. 如何理解计算机的层次结构？ 答：计算机硬件、系统软件和应用软件构成了计算机系统的三个层次结构。 （1）硬件系统是最内层的，它是整个计算机系统的基础和核心。 （2）系统软件在硬件之外，为用户提供一个基本操作界面。 （3）应用软件在最外层，为用户提供解决具体问题的应用系统界面。 通常将硬件系统之外的其余层称为虚拟机。各层次之间关系密切，上层是下层的扩展，下层是上层的基础，各层次的划分不是绝对的。 3. 说明高级语言、汇编语言和机器语言的差别及其联系。 答：机器语言是计算机硬件能够直接识别的语言，汇编语言是机器语
言的符号表示，高级语言是面向算法的语言。高级语言编写的程序（源程序）处于最高层，必须翻译成汇编语言，再由汇编程序汇编成机器语言（目标程序）之后才能被执行。 4. 如何理解计算机组成和计算机体系结构？ 答：计算机体系结构是指那些能够被程序员所见到的计算机系统的属性，如指令系统、数据类型、寻址技术组成及I/O机理等。计算机组成是指如何实现计算机体系结构所体现的属性，包含对程序员透明的硬件细节，如组成计算机系统的各个功能部件的结构和功能，及相互连接方法等。 5. 冯?诺依曼计算机的特点是什么？ 解：冯?诺依曼计算机的特点是：P8 ●计算机由运算器、控制器、存储器、输入设备、输出设备五大 部件组成； ●指令和数据以同同等地位存放于存储器内，并可以按地址访 问； ●指令和数据均用二进制表示； ●指令由操作码、地址码两大部分组成，操作码用来表示操作的 性质，地址码用来表示操作数在存储器中的位置； ●指令在存储器中顺序存放，通常自动顺序取出执行； ●机器以运算器为中心（原始冯?诺依曼机）。
第三章 上下文无关语言 3.1 略。 3.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 1 S →aS|T|ε T →bTc|ε 对B,构造CFG C 2 S →Sc|R|ε R →aRb 由此知 A,B 均为上下文无关语言。 但是由例3.20, A ∩B={a n b n c n |n ≥0}不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。 b.用反证法。假设CFL 在补运算下封闭，则对于(a)中上下文无关语言A,B ，A ,B 也为CFL ，且CFL 对并运算封闭，所以B A ?也为CFL ，进而知道B A ?为CFL ，由DeMorgan 定律B A ?＝A ∩B ，由此A ∩B 是CFL,这与(a)的结论矛盾，所以CFL 对补运算不封闭。 3.3 略。 3.4和3.5 给出产生下述语言的上下文无关文法和PDA ，其中字母表∑={0,1}。 a. {w | w 至少含有3个1} S →A1A1A1A A →0A|1A|ε b. {w | w 以相同的符号开始和结束} S →0A0|1A1 A →0A|1A|ε c. {w | w 的长度为奇数} S →0A|1A A →0B|1B|ε B →0A|1A 0, ε→ε 0,ε→ε 0,ε→ε 1,ε→ε 0,ε→ε
矩阵论复习题 1. 设+=R V 是正实数集,对于任意的V y x ∈,,定义x 与y 的和为 y x y x ?=⊕ 对于任意的数R k ∈,定义k 与x 的数乘为 k x x k =? 问:对于上述定义加法和数乘运算的集合V ,是否构成线性空间,并说明理由. 2.对任意的2,R y x ∈,),(21x x x =,),(21y y y =定义x 与y 的和为 ),(112211y x y x y x y x +++=⊕ 对于任意的数R k ∈,定义k 与x 的数乘为 )2 )1(,(2121x k k kx kx x k -+=? 问:对于上述定义加法和数乘运算的集合2R ,是否构成线性空间,并说明理由. 3．设},022|),,{(321321R x x x x x x x S i ∈=++=，试证明S 是3R 的子空间，并求S 的一组基和S dim . 4.设)(R P n 表示次数不超过n 的全体多项式构成的线性空间, )}()(,0)0(|)({R P x f f x f S n ∈='= 证明S 是)(R P n 的子空间,并写出S 的一组基和计算S dim . 5. 设33:R R T →是线性变换， ()()321323213212,,2,,x x x x x x x x x x x T -++-+= 求T 的零空间)(T N 和像空间)(T R 的基和维数. 6. 设T 是3R 上的线性变换,对于基},,{k j i 有 k j k j i T -=++)( i k j T =+)( k j i k T 532)(++= 1)确定T 在基},,{k j i 下的矩阵; 2)求T 的像空间的基与维数.
习题 一 1．（1）因 cos sin sin cos nx nx nx nx ?? ? ? -?? cos sin sin cos x x x x ????-??= cos(1) sin(1)sin(1) cos(1)n x n x n x n x ++?? ??-++?? ，故由归纳法知 cos sin sin cos n nx nx A nx nx ?? =??-?? 。 （2）直接计算得4A E =-，故设4(0,1,2,3)n k r r =+=，则4(1)n k r k r A A A A ==-，即只需算出2 3 ,A A 即可。 （3）记J=0 1 0 1 1 0 ?????? ?????????? ，则 ， 1122111 11 () n n n n n n n n n n n n n n i i n i n n i n n n a C a C a C a C a C a A aE J C a J a C a a -----=-?????? ??=+==?? ???????? n ∑。 2．设112 2 (1,0),0 a A P P a A E λλ-??===???? 则由得 2 1112111 1 1 210 0 0 a λλλλλλλ?? ????==?????????????? 1时,不可能。 而由2 112 222 0 0 000 0 0 a λλλλλλ??????==?????????????? 1时,知1i λ=±所以所求矩阵为1 i PB P -， 其中P 为任意满秩矩阵，而 1231 0 1 0 1 0,,0 10 1 0 1B B B -?????? ===?????? --?????? 。 注：2A E =-无实解，n A E =的讨论雷同。 3．设A 为已给矩阵，由条件对任意n 阶方阵X 有AX=XA ，即把X 看作2 n 个未知数时线 性方程AX -XA=0有2 n 个线性无关的解，由线性方程组的理论知其系数矩阵为零矩
作业解答 第一章作业解答 1.1 基本的软件系统包括哪些内容？ 答：基本的软件系统包括系统软件与应用软件两大类。 系统软件是一组保证计算机系统高效、正确运行的基础软件，通常作为系统资源提供给用户使用。包括：操作系统、语言处理程序、数据库管理系统、分布式软件系统、网络软件系统、各种服务程序等。 1.2 计算机硬件系统由哪些基本部件组成？它们的主要功能是什么？ 答：计算机的硬件系统通常由输入设备、输出设备、运算器、存储器和控制器等五大部件组成。 输入设备的主要功能是将程序和数据以机器所能识别和接受的信息形式输入到计算机内。 输出设备的主要功能是将计算机处理的结果以人们所能接受的信息形式或其它系统所要求的信息形式输出。 存储器的主要功能是存储信息，用于存放程序和数据。 运算器的主要功能是对数据进行加工处理，完成算术运算和逻辑运算。 控制器的主要功能是按事先安排好的解题步骤，控制计算机各个部件有条不紊地自动工作。 1.3 冯·诺依曼计算机的基本思想是什么？什么叫存储程序方式？ 答：冯·诺依曼计算机的基本思想包含三个方面： 1) 计算机由输入设备、输出设备、运算器、存储器和控制器五大部件组成。 2) 采用二进制形式表示数据和指令。 3) 采用存储程序方式。 存储程序是指在用计算机解题之前，事先编制好程序，并连同所需的数据预先存入主存储器中。在解题过程（运行程序）中，由控制器按照事先编好并存入存储器中的程序自动地、连续地从存储器中依次取出指令并执行，直到获得所要求的结果为止。 1.4 早期计算机组织结构有什么特点？现代计算机结构为什么以存储器为中心？ 答：早期计算机组织结构的特点是：以运算器为中心的，其它部件都通过运算器完成信息的传递。 随着微电子技术的进步，人们将运算器和控制器两个主要功能部件合二为一，集成到一个芯片里构成了微处理器。同时随着半导体存储器代替磁芯存储器，存储容量成倍地扩大，加上需要计算机处理、加工的信息量与日俱增，以运算器为中心的结构已不能满足计算机发展的需求，甚至会影响计算机的性能。为了适应发展的需要，现代计算机组织结构逐步转变为以存储器为中心。 1.5 什么叫总线？总线的主要特点是什么？采用总线有哪些好处？ 答：总线是一组可为多个功能部件共享的公共信息传送线路。 总线的主要特点是共享总线的各个部件可同时接收总线上的信息，但必须分时使用总线发送信息，以保证总线上信息每时每刻都是唯一的、不至于冲突。 使用总线实现部件互连的好处： ①可以减少各个部件之间的连线数量，降低成本； ②便于系统构建、扩充系统性能、便于产品更新换代。 1.6 按其任务分，总线有哪几种类型？它们的主要作用是什么？ 答：按总线完成的任务，可把总线分为：CPU内部总线、部件内总线、系统总线、外总线。
习题二 1．化下列矩阵为Smith 标准型： （1）222211λλλλ λλλλλ?? -?? -????+-?? ; （2）2222 00 000 00(1)00000λλλλλλ ?? ?? -? ? ??-?? -?? ; （3）2222 232321234353234421λλλλλλλλλλλλλλ?? +--+-??+--+-????+---?? ; (4)23014360220620101003312200λλλλλλλλλλλλλλ????++??????--????---?? . 解：（1）对矩阵作初等变换 23221311(1)100 10 000000(1)00(1)c c c c c c r λλλλλλλλλ+--?-???????????→-???→? ??? ????-++???? ， 则该矩阵为Smith 标准型为 ???? ? ?????+)1(1λλλ； （2）矩阵的各阶行列式因子为 44224321()(1),()(1),()(1),()1D D D D λλλλλλλλλλ=-=-=-=, 从而不变因子为 22 2341234123()()() ()1,()(1),()(1),()(1)()()() D D D d d d d D D D λλλλλλλλλλλλλλλλ== =-==-==-故该矩阵的Smith 标准型为
2210000(1)0000(1)00 00(1)λλλλλλ?? ??-????-?? -??； （3）对矩阵作初等变换 故该矩阵的Smith 标准型为 ?? ?? ??????+--)1()1(112 λλλ; (4)对矩阵作初等变换 在最后的形式中，可求得行列式因子 3254321()(1),()(1),()()()1D D D D D λλλλλλλλλ=-=-===, 于是不变因子为 2541234534()() ()()()1,()(1),()(1)()() D D d d d d d D D λλλλλλλλλλλλλ==== =-==-故该矩阵的Smith 标准形为 2 1 0000 010 0000100000(1)00 00 0(1)λλλλ?????????? -?? ??-?? . 2.求下列λ-矩阵的不变因子： （1） 21 0021002λλλ--????--????-??； （2）100 1000 λαββλα λαββ λα+????-+? ???+??-+?? ；
二章-信息量和熵习题解 2.1 莫尔斯电报系统中，若采用点长为0.2s ，1划长为0.4s ，且点和划出现的概率分别为2/3和1/3，试求它的信息速率(bits/s)。 解: 平均每个符号长为: 15 44.0312.032=?+?秒 每个符号的熵为9183.03log 3 123log 32=?+?比特/符号 所以，信息速率为444.34159183.0=?比特/秒 2.2 一个8元编码系统，其码长为3，每个码字的第一个符号都相同(用于同步)，若每秒产生1000个码字，试求其信息速率(bits ／s)。 解: 同步信号均相同不含信息,其余认为等概,每个码字的信息量为 3*2=6 比特； 所以，信息速率为600010006=?比特/秒 2.3 掷一对无偏的骰子，若告诉你得到的总的点数为：(a ) 7；(b ) 12。 试问各得到了多少信息量? 解: (a)一对骰子总点数为7的概率是 36 6 所以，得到的信息量为 585.2)36 6(log 2= 比特 (b) 一对骰子总点数为12的概率是36 1 所以，得到的信息量为 17.5361log 2= 比特 2.4 经过充分洗牌后的一付扑克(含52张牌)，试问： (a) 任何一种特定排列所给出的信息量是多少? (b) 若从中抽取13张牌，所给出的点数都不相同时得到多少信息量? 解: (a)任一特定排列的概率为! 521, 所以，给出的信息量为 58.225!521log 2 =- 比特 (b) 从中任取13张牌,所给出的点数都不相同的概率为 1313 1313525213!44A C ?=
所以，得到的信息量为 21.134 log 1313522=C 比特. 2.5 设有一个非均匀骰子，若其任一面出现的概率与该面上的点数成正比，试求各点 出现时所给出的信息量，并求掷一次平均得到的信息量。 解:易证每次出现i 点的概率为 21i ,所以 比特比特 比特 比特 比特 比特 比特 398.221 log 21)(807.1)6(070.2)5(392.2)4(807.2)3(392.3)2(392.4)1(6,5,4,3,2,1,21 log )(2612=-==============-==∑=i i X H x I x I x I x I x I x I i i i x I i 2.6 园丁植树一行，若有3棵白杨、4棵白桦和5棵梧桐。设这12棵树可随机地排列， 且每一种排列都是等可能的。若告诉你没有两棵梧桐树相邻时，你得到了多少关 于树的排列的信息? 解: 可能有的排列总数为 27720! 5!4!3!12= 没有两棵梧桐树相邻的排列数可如下图求得， Y X Y X Y X Y X Y X Y X Y X Y 图中X 表示白杨或白桦，它有???? ??37种排法，Y 表示梧桐树可以栽种的位置，它有? ??? ??58种排法， 所以共有???? ??58*??? ? ??37=1960种排法保证没有两棵梧桐树相邻， 因此若告诉你没有两棵梧桐树相邻时，得到关于树排列的信息为1960log 27720log 22-=3.822 比特 2.7 某校入学考试中有1/4考生被录取，3/4考生未被录取。被录取的考生中有50%来 自本市，而落榜考生中有10％来自本市，所有本市的考生都学过英语，而外地落榜考生中以及被录取的外地考生中都有40%学过英语。 (a) 当己知考生来自本市时，给出多少关于考生是否被录取的信息?
习题三 1．证明下列问题： （1）若矩阵序列{}m A 收敛于A ，则{}T m A 收敛于T A ，{} m A 收敛于A ； （2）若方阵级数∑∞ =0m m m A c 收敛，则∑∑∞ =∞==?? ? ??00)(m m T m T m m m A c A c . 证明：（1）设矩阵 ,,2,1,)() ( ==?m a A n n m ij m 则 ,)()(n n m ji T m a A ?=,)()(n n m ij m a A ?=,,2,1 =m 设 ,)(n n ij a A ?= 则 n n ji T a A ?=)(，,)(n n ij a A ?= 若矩阵序列{}m A 收敛于A ，即对任意的n j i ,,2,1, =，有 ij m ij m a a =∞ →) (lim ， 则 ji m ji m a a =∞ →)(lim ，ij m ij m a a =∞ →)(lim ，n j i ,,2,1, =， 故{} T m A 收敛于T A ，{} m A 收敛于A . (2)设方阵级数 ∑∞ =0 m m m A c 的部分和序列为 ,,,,21m S S S ， 其中m m m A c A c c S +++= 10.
若 ∑∞ =0 m m m A c 收敛，设其和为S ，即 S A c m m m =∑∞ =0 ，或S S m m =∞ →lim ， 则 T T m m S S =∞ →lim . 而级数∑∞ =0 )(m m T m A c 的部分和即为T m S ，故级数∑∞ =0 )(m m T m A c 收敛，且其和为T S ， 即 ∑∑∞ =∞==?? ? ??00)(m m T m T m m m A c A c . 2.已知方阵序列{}m A 收敛于A ，且{} 1-m A ，1 -A 都存在，证明： （1）A A m m =∞ →lim ；（2）{}1 1 lim --∞ →=A A m m . 证明：设矩阵 ,,2,1,)() ( ==?m a A n n m ij m ,)(n n ij a A ?= 若矩阵序列{}m A 收敛于A ，即对任意的n j i ,,2,1, =，有 ij m ij m a a =∞ →) (lim . (1) 由于对任意的n j j j ,,,21 ，有 ,lim ) (k k kj m kj m a a =∞ → n k ,,2,1 =， 故 ∑-∞ →n n n j j j m nj m j m j j j j m a a a 2121)()(2)(1) ()1(lim τ ＝ ∑-n n n j j j nj j j j j j a a a 21212121) ()1(τ ， 而 ∑-= n n n j j j m nj m j m j j j j m a a a A 2121) ()(2)(1)()1(τ，
计算理论习题答案CHAP2new
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 1 S →aS|T|ε T →bTc|ε 对B,构造CFG C 2 S →Sc|R|ε R →aRb 由此知 A,B 均为上下文无关语言。 但是由例3.20, A ∩B={a n b n c n |n ≥0}不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。 b.用反证法。假设CFL 在补运算下封闭，则对于(a)中上下文无关语言A,B ， A , B 也为CFL ，且CFL 对并运算封闭，所以B A ?也为CFL ，进而知道B A ?为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|ε ε,1→ 1, 0, ε,1→ ε,1→
b. {w | w 以相同的符号开始和结束} S →0A0|1A1 A →0A|1A|ε c. {w | w 的长度为奇数} S →0A|1A A →0B|1B|ε B →0A|1A d. {w | w 的长度为奇数且正中间的符号为0} S →0S0|1S1|0S1|1S0|0 e. {w | w 中1比0多} S →A1A 1,ε→ 0,ε→0,ε→1,1→ 0,0→0,ε→1,ε→0,ε→0,ε→ 0,ε→0,0→ε,ε→ ε,$→
第二章习题解答 P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: 568 56534 30127012010??????????????????D DD DDD NDD ND N D DD ND N D DD DDD DDDD NDDD NDD ND N 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法： E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ?+?+?+?+?+?+?+?+??????+?+?+?+?+?+********()*()*()*()*()*()*() 最右推导: E E T E T F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树：/********************************
练习一： 1．设A 、是Hermite 矩阵，证明：AB 是Hermite 矩阵的充分必要条件是n n C B ?∈AB=BA 。2．设，若，则A 为反Hermite 矩阵。试证明：任意一个都n n C A ?∈A A H -=n n C B ?∈可以唯一地表示为一个Hermitet 矩阵与一个反Hermite 矩阵的和。3．证明反Hermite 矩阵的主对角线上的元素或为零，或为纯虚数。4．设是Hermite 矩阵，rank(A)=1，证明：矩阵A 的主对角线上凡不是零的元素n n C A ?∈都是具有同符号的实数；又设是反Hermite 矩阵，rank(B)=1，证明：矩阵B n n C B ?∈的主对角线上凡不是零的元素都是具有同符号的虚部之纯虚数。5．试求一酉矩阵P ，使为对角矩阵，这里AP P AP P H =-1（1）A=； （2）A=。??????????----10001i i i i ??????????-0010010i i 6. 设是Hermite 矩阵。证明A 是Hernite 正定矩阵的充分必要条件是，存在n n C A ?∈Hermite 正定矩阵B ，使得。2 B A =7．设是Hermite 矩阵,则下列条件等价：n n C A ?∈ （1）A 是Hernite 半正定矩阵； （2）A 的特征值全为非负实数； （3）存在矩阵，使得。n n C P ?∈P P A H =练习二：1．用初等变换化下列多项式矩阵为Smith 标准形：（1） ； （2）；()???? ??+-=λλλλλλλ352223A ()??????????-+--=222211λλλλλλλλλλB （3） ；（4）()()220000 001C λλλλλ??+??=????+????。()()??????????????---=00000100000002222λλλλλλλD 2．求下多项式矩阵的不变因子：
练习 1.1 图给出两台DFA M 1和M 2的状态图. 回答下述有关问题. a. M 1的起始状态是q 1 b. M 1的接受状态集是{q 2} c. M 2的起始状态是q 1 d. M 2的接受状态集是｛q 1，q 4｝ e. 对输入aabb,M 1经过的状态序列是q 1，q 2，q 3，q 1，q 1 f. 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}; 3 415）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}; 3 324）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中给出。试画出此机器的状态图。 d
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} 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 1
习题一 1.判断下列集合对指定的运算是否构成R 上的线性空间 （1）11 {()| 0}n ij n n ii i V A a a ?====∑，对矩阵加法和数乘运算； （2）2{|,}n n T V A A R A A ?=∈=-，对矩阵加法和数乘运算； （3）33V R =；对3R 中向量加法和如下定义的数乘向量：3 ,,0R k R k αα?∈∈=； （4）4{()|()0}V f x f x =≥，通常的函数加法与数乘运算。 解： （1）、（2）为R 上线性空间 （3）不是，由线性空间定义，对0α?≠有1α=α，而题（3）中10α= （4）不是，若k<0，则()0kf x ≤，数乘不满足封闭性。 2.求线性空间{|}n n T V A R A A ?=∈=的维数和一组基。 解：一组基 100 010 10 101010000000100............ ......0010010?? ???? ?????? ???? ? ? ? ? ? ??? ? ? ? ? ? ??? ? ? ? ? ? ??? ? ? ? ? ? ??? ? ? ? ? ? ?? ? ? ? ? ? ?? ? ? ? ? ? ?? ? ? ? ? ? ?? ? ? ? ? ? ?? ?? ? ? ?? ?? ? ? ? ?????? dim W =n ( n +1)/2 3.如果U 1和U 2都是线性空间V 的子空间，若dim U 1=dim U 2，而且12U U ?，证明：U 1=U 2。 证明：因为dim U 1=dim U 2，故设 {}12,,,r ααα为空间U 1的一组基，{}12,,,r βββ为空间U 2的一组基 2U γ?∈，有 ()12 r X γγβββ= 而 ()()12 12r r C αααβββ=，C 为过渡矩阵，且可逆 于是 ()()()112 12121r r r X C X Y U γγγγβββαααααα-===∈ 由此，得 21 U U ?
n k r n n 1 2 习题 一 1．（ 1）因 cosnx sin nx sin nx cosnx cosx sin x sin x = cosx cos(n sin(n 1)x 1)x sin( n cos(n 1)x 1)x ，故由归纳法知 cosnx sin nx A 。 sin nx cosnx （ 2）直接计算得 A 4 E ，故设 n 4 k r (r 0,1,2,3) ，则 A n A 4 k A r ( 1) A ， 即 只需算出 A 2, A 3 即可。 0 1 0 1 （ 3 ）记 J= ，则 ， 1 0 n 1 n 1 2 n 2 n a C n a C n a C n a n C 1 a n 1 C n 1a A n (aE J ) n n C i a i J n i i 0 n n a n 。 C 1a n 1 a n 2. 设 A P 1 a 2 P 1(a 1,0),则由A 2 E 得 a 1时, 1 1 1 1 0 1 2 1 2 1 0 2 不可能。 1 而由 a 1 0时, 2 1 知 1 所以所求矩阵为 PB P 1 ， 其中 P 为任意满秩矩阵，而 i i 2 2 2 1 0 1 0 1 0 B 1 , B 2 , B 3 。 0 1 0 1 1 注： A 2 E 无实解， A n E 的讨论雷同。 3. 设 A 为已给矩阵，由条件对任意 n 阶方阵 X 有 AX=XA ，即把 X 看作 n 2 个未知数时线 性方程 AX XA=0 有 n 2 个线性无关的解， 由线性方程组的理论知其系数矩阵为零矩阵， 1
计算理论习题解答 练习 1.1 图给出两台DFA M1和M2的状态图. 回答下述有关问题. a.M1的起始状态是q1 b.M1的接受状态集是{q2} c.M2的起始状态是q1 d.M2的接受状态集是｛q1，q4｝ e.对输入aabb,M1经过的状态序列是q1，q2，q3，q1，q1 f.M1接受字符串aabb吗？否 g.M2接受字符串ε吗？是 1.2 给出练习 2.1中画出的机器M1和M2的形式描述. M1=(Q1,Σ,δ1,q1,F1) 其中 1）Q1={q1,q2,q3,}; 2）Σ={a,b}; 3 41 5）F1={q2} M2=(Q2,Σ,δ2,q2,F2) 其中 1）Q2={q1,q2,q3,q4}; 2）Σ={a,b}; 3 3）q2是起始状态 4）F2={q1,q4} 1.3 DFA M的形式描述为( {q1，q2，q3，q4，q5}，{u,d},δ,q3，{q3}),其中δ在表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} h){w | w 是除11和111以外的任何字符} i){w | w 的奇位置均为1} j) {w | w 至少含有2个0，且至多含有1个1} k) {ε,0} l) {w | w 含有偶数个0，或恰好两个1} m) 空集 n) 除空串外的所有字符串 1.7 给出识别下述语言的NFA ，且要求符合规定的状态数。 0,1 1
7.3 a. 当Y=0时，输出X=1，所以1274和10505是互素的。 7.4 对于字符串w=baba和下面的文法CFG G，试填写定理8.14中识别上下文无关语言的多项式时间算法中所描述的表。 S→RT R→TR|a T→RT|b 解：
7.5 下面的公式是可满足得吗？ φ=(x∨y)∧(x∨y)∧(x∨y)∧( x∨y) 解:(x,y)共有四种取值：(true, true),(true, false),(false, true),(false, false).分别将其带入公式得： 若(x,y)=(true, true)，φ=(true∨true) ∧ (true∨false) ∧ (false∨true) ∧(false∨false)=false 若(x,y)=(true, false)，φ=(true∨false) ∧ (true∨true) ∧ (false∨false) ∧ (false∨true)=false 若(x,y)=(false, true)，φ=(false∨true) ∧ (false∨false) ∧ (true∨true) ∧ (true∨false)=false 若(x,y)=(false, false),φ=(false∨false) ∧(false∨true) ∧(true∨false) ∧ (true∨true)=false 所以原公式不可满足。 7.6 证明P在并、连接和补运算下封闭。 (1) 并： 对任意 L 1, L 2 ∈P，设有n a时间图灵机M 1 和n b时间图灵机M 2 判定它们， 且c=max{a,b}。 对L 1?L 2 构造判定器M: M=“对于输入字符串w : 1)在w上运行M 1，在w上运行M 2 。
第一章 1.1 图给出两台DFA M 1和M 2 的状态图. 回答下述有关问题. a.M 1的起始状态是q 1 b.M 1的接受状态集是{q 2 } c.M 2的起始状态是q 1 d.M 2的接受状态集是｛q 1 ，q 4 ｝ e.对输入aabb,M 1经过的状态序列是q 1 ，q 2 ，q 3 ，q 1 ，q 1 f.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}; 3）δ 1 为： 4）q 1 是起始状态 5）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}; 3）δ 2 为： 3）q 2 是起始状态
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} d
e) {w | w 从0开始且为奇长度，或从1开始且为偶长度} 或 f) {w | w 不含子串110} g) {w | w 的长度不超过5} 1个1} k) {ε,0} 0,1 1
Operation X Y 127410505 X mod Y X127410505 X Y105051274 X mod Y X3131274 X Y1274313 X mod Y X22313 X Y31322 X mod Y X522 X Y225 X mod Y X25 X Y52 X mod Y X12 X Y21 X mod Y X01 X Y10当Y=0时，输出X=1，所以1274和10505是互素的。 对于字符串w=baba和下面的文法CFG G，试填写定理中识别上下文无关语言的多项式时间算法中所描述的表。 S RT R TR|a T RT|b
T R,T S R,T,S R S S T R,T R 下面的公式是可满足得吗 =(x y)(x y)(x y)( x y) 解:(x,y)共有四种取值：(true, true),(true, false),(false, true),(false, false).分别将其带入公式得： 若(x,y)=(true, true)，=(true true) (true false) (false true) (false false)=false 若(x,y)=(true, false)，=(true false) (true true) (false false) (false true)=false 若(x,y)=(false, true)，=(false true) (false false) (true true) (true false)=false 若(x,y)=(false, false),=(false false) (false true) (true false) (true true)=false 所以原公式不可满足。 证明P在并、连接和补运算下封闭。 (1) 并：
|讪 而由a = 0时， 〔0 其中P 为任意满秩矩阵，而 注：A = -E 无实解，A n =E 的讨论雷同。 性方程AX -XA=0有n 2 个线性无关的解，由线性方程组的理论知其系数矩阵为零矩阵, 习题 -cosnx sin nx[ 1-("因[L sinnxcosnx 丄sin C0SX sin x = COs(n 1)x sin(n 1)x ，故由归纳法知 x cosx f-sin(n 1)x cos(n 1)x A n cosnx sin nx '-sinnx cosnx (2)直接计算得 A 4 - -E ，故设 n =4k r(r =0,1,2,3)，则 A n = A 4k A r =(-1)k A r ，即 只需算出A 2, A 3即可。 (3 )记 J= ，则 a n C ：a n n i i n _i_ A =(aE J) = 6 C n a J i =0 n 』亠2 n _2 C n a C ；a nJ n a III c ：〕 III c^a C ： a n 」 n a 2?设 A =P F a 1 -0 /一 2 _ P’yo),则由 A 2 =E 得 冷0 1 〔0 1 一 ,B 2 = 【0 -0] ，艮 0] 。 -1 i 0 -k 0 1 2 _0 所以所求矩阵为PB i P’ , 3?设A 为已给矩阵，由条件对任意 n 阶方阵 X 有AX=XA ，即把X 看作n 个未知数时线
通过直接检验即发现 A 为纯量矩阵。a n ? a n 1 ■ 11（ ? = 0 5.先证A 或B 是初等到阵时有 AB *=B *A * ，从而当A 或B 为可逆阵时有 AB 、B *A *。 考虑到初等变换 A 对B 的n 阶子行列式的影响及 A 二A‘即可得前面提到的结果。 下设PAQ = E r 0 ,（这里P , Q 满秩），则由前讨论只需证下式成立即可: 〔0。」 6 .由 r(A)二 r(A —)及 AX 二 0= (AX)—AX = 0，即 AX = 0 与 A —AX = 0 同解，此即所 求证。 7.设其逆为 a j ，则当I 固定时由可逆阵的定义得 n 个方程 .i 1 . 1 2 . 1 n-1 ? a
相关主题
文本预览