2006年秋《计算理论基础》本科生试卷 填空题 1、确定型有穷自动机的形式定义是一个5元组(Q，∑，δ，q0，F)其中： (1)Q为有穷状态集，（2）∑有穷字母表，（3）δ(q,a)是转移函数，它的第1个自变量为q∈Q，第二个自变量a∈∑，其结果δ(q,a)∈Q，即为Q×∑→Q的函数（映射），（4）q0为初始状态(一般只有一个)，（5）F有一些接受状态（可以为多个。 2、非确定型有穷自动机N接受字符串w=b1b2…b m，是指存在状态序列r0,r1,…,r m,且满足：（1）r0=q0；（2）r i+1∈δ(r i,a i+1) (i=0,1,…,m-1)，(3)r m∈F。 3、正则表达式的定义是：（1）a∈∑，空串ε，空集Φ均为合法的正则表达式，（2）若R1，R2是正则表达式，则(R1?R2)、R1?R2、R1*均是正则表达式。 4、将正则表达转换成自动机时，先建立单个字符的自动机，再用并、连、星号运算得到复杂正则表达的自动机，而将自动机转换为正则表达式时，需要先建立新开始状态与一个新接受态，在新开始状态与原开始状态之间连上空串边，在原来所有的接受状态与新接受状态间连空串边。 5、对于正则语言A的任意字符串s，当其长度≥p（泵长度）时，则一定存在满足|y|>0、|xy|≤p分解方式S=xyz，使得任意i≥0，xy i z∈A。这是正则语言的性质，基于此性质并利用反证法可证明一个语言不是正则语言，这时需要验证满足“|y|>0、|xy|≤p”的每种可能分解方式，都不满足“任意i≥0，xy i z∈A”。 6、非确定型下推自动机PDA接受w=w1w2…w m，是指存在状态序列r0,r1,…,r m，栈字字符串序列s0,s1,…,s m∈Γ*，满足：（1）r0=q0,s0=ε；（2）(r i+1,b)∈δ(r i,w i+1,a)，其中s i=at(此时a 为栈顶元素)，s i+1=bt(b为当前动作后的栈顶元素)；（3）r m∈F,s m=ε。 7、Turing机特点：（1）可以从输送带中读出字符，也可以修改输入带中的字符；（2）可沿输入带向右移动直到遇到字符串结束标志为止，也可从右向左移动直到遇到左端标志为止；（3）可以边读写边移动读写头，也可以不读写而单纯移动；（4）如果进入了“接受”状态则停机(不必消耗所有字符)，如果进入了“拒绝”状态也停机，否则一直运行，永不停机。 8、图灵机的形式定义是7元组(Q,∑,Γ,δ,q0,q accept,q reject)，其中：（1）Q为状态集；（2）∑为输入字母表，不包括空白符号；（3）Γ为带字母表，包括∑与空格；（4）δ：Q?Γ→Q?Γ?{L,R}，转换函数，第1个自变量的取值范围是Q，第2个自变量的取值范围是Γ，其值域是一个三元组，第一个分量表示下一个状态，第二个分量表示写入到输入带上的字符，第三个分量表示下一步的位置；（5）q0∈Q是初始状态；（6）q accept∈Q是接受状态；（7）q reject∈Q拒绝状态，且q reject≠q accept。 9、图灵机M接受字符串w，是指存在一系列的格局C1,C2,…,C k，使得：（1）C1是M 在输入w的起始格局，即C1=q0w；（2）每个C i确定地产生C i+1；（3）Ck是接受格局，即从起始格局起，经过有限步后可达到接受格局。 二、简述题 1、每个多带图灵机等价于某台单带图灵机。请参考下图陈述单带图灵机描述多带图灵机的的细节。多带图灵机为M，待的单带图灵机记为S。
形式语言与自动机课后习题答案 第二章 4．找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。 答：G={N,T,P,S} 其中N={S,A,B,C,D} T={x,y} 其中x ∈{所有字母} y ∈{所有的字符} P 如下: S →x S →xA A →y A →yB B →y B →y C C →y C →y D D →y 6．构造上下文无关文法能够产生 L={ω/ω∈{a,b}*且ω中a 的个数是b 的两倍} ! 答：G={N,T,P,S} 其中N={S} T={a,b} P 如下: S →aab S →aba S →baa S →aabS S →aaSb S →aSab S →Saab S →abaS S →abSa S →aSba S →Saba S →baaS S →baSa S →bSaa S →Sbaa 7．找出由下列各组生成式产生的语言（起始符为S ） (1) S →SaS S →b (2) S →aSb S →c (3) / (4) S →a S →aE E →aS 答：（1）b(ab)n /n ≥0}或者L={(ba)n b /n ≥0} (2) L={a n cb n /n ≥0} (3) L={a 2n+1 /n ≥0} 第三章 1． 下列集合是否为正则集，若是正则集写出其正则式。 （1） 含有偶数个a 和奇数个b 的{a,b}*上的字符串集合 （2） 含有相同个数a 和b 的字符串集合 （3） < （4） 不含子串aba 的{a,b}*上的字符串集合 答：（1）是正则集，自动机如下 a
a (2) 不是正则集，用泵浦引理可以证明，具体见17题（2）。 (3) 是正则集 先看L’为包含子串aba的{a,b}*上的字符串集合 { 显然这是正则集，可以写出表达式和画出自动机。（略）则不包含子串aba的{a,b}*上的字符串集合L是L’的非。 根据正则集的性质，L也是正则集。 4．对下列文法的生成式，找出其正则式 （1）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→abS A→bB B→b B→cC C→D D→bB … D→d （2）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→cC A→bB B→bB B→a C→D C→abB D→d 答：(1) 由生成式得： S=aA+B ① A=abS+bB ② ] B=b+cC ③ C=D ④ D=d+bB ⑤ ③④⑤式化简消去CD，得到B=b+c(d+bB) 即B=cbB+cd+b =>B=(cb)*(cd+b) ⑥ 将②⑥代入① S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =>S=(aab)*(ab+ε)(cb)*(cd+b) (2) 由生成式得： S=aA+B ① A=bB+cC ② … B=a+bB ③ C=D+abB ④ D=dB ⑤ 由③得B=b*a ⑥
形式语言与自动机的发展和在计算理论中的作用 2015060104020王桢 形式语言是语言学衍生过来的，开始形式语言并没有用于研究计算机编程语言，而只是研究自然语言的结构。在电子计算机出现以后，人们就马上想到用计算机来作自然语言的机械翻译。可是这项工作并没有所成果，对自然语言的结构 理解太片面化，翻译质量不理想也很难提高。1956年，乔姆斯基发表了用形 式语言方法研究自然语言的第一篇文章。他对语言进行定义：给定一组符号，称 为字母表，用∑表示。又用∑*表示∑中字母组成的所有符号串的集合。∑*的每个子集都是∑上的一个语言。乔姆斯基的语言定义方法为人们所公认，一直沿用下来，乔姆斯基根据文法将语言分成3大类。同时克林在研究神经细跑中，建立 了识别语言的系统有穷状态自动机。乔姆斯基发现自动机和文法分别从生成和识别去表达语言，并建立了形式文法和自动机之间的联系，证明语言的形式文法与自动机之间存在着如下的对应关系：①若某一语言能用图灵机来识别，则它就能 用O型文法生成，反之亦然；②若某一语言能用线性有界自动机来识别，则它 就能用上下文敏感文法生成，反之亦然；③若某一语言能用后进先出自动机来识别，则它就能用上下文自由文法生成，反之亦然；④若某一语言能用有限自动机来识别，则它就能用有限状态文法生成，反之亦然。这一成果将形式语言引入数 学，使得形式语言真正诞生。1960年，算法语言ALGOL60报告发表。1961年，又发表了ALGOL60修改报告。在这两个报告中，第一次使用一种称为BNF 范式的形式方法来描述程序设计语言ALGOL60的语法。不久，人们即发现BNF 范式极其类似于形式语言理论中的上下文无关文法，从而打开了形式语言广泛应用于程序设计语言的局面，并给形式语言理论本身的研究以极大的推动，使它发展成为理论计算机科学的一个重要分支。 形式语言理论是从语言学衍生而来，作为一种理解自然语言的句法规律。在发展过程中人们发现其在计算机语言中的作用，计算机语言在计算机科学中，形式语言通常作为定义编程语言和语法的基础。对编程语言编译，使之转换成机器语言，形式语言在这一工作中有很重要的作用。形式语言推动了计算机学科的发展，并成为计算机学科里重要的分支。 19世纪中，布尔用数学方法研究思维规律的问题建立了逻辑代数，即布尔代数。肖斯塔科夫和仙农，独立地应用布尔代数于继电器接点电路的分析和综合,
D、人造机器人 答案：C PEAS分别是指哪些组件？ A、性能/环境/执行器/传感器 B、传感器/性能/环境/执行器 C、环境/执行器/传感器/性能 D、传感器/环境/执行器/性能 答案：A 智能体程序分别有哪些类型？（） A、感知智能体/决策智能体/学习智能体/规划智能体 B、简单反射型智能体/基于模型的反射型智能体/基于目标的智能体/基于效用的智能体 C、机器人/软件/硬件/算法 D、类人智能体/类动物智能体 答案：B 智能体使用什么组件来获得环境信息？（） A、执行器 B、CPU C、传感器 D、条件--行动规律 答案：C 基于模型的反射型智能体的核心组件比简单反射型智能体多了什么？（） A、执行器 B、传感器 C、CPU D、世界模型 答案：D 基于目标的智能体比基于模型的反射型智能体多了什么组件？（） A、CPU B、世界模型 C、目标 D、环境 答案：C 可以把效用想象成什么？（） A、效果 B、能源 C、金钱 D、智能体 答案：C 基于效用的智能体比基于目标的智能体多了什么核心组件？（） A、世界模型 B、CPU C、效用评估 D、金钱
答案：C 哪个例子是强链接？（） A、收音机听到的一个人 B、微博上的陌生朋友 C、亲人 D、同事 答案：CD 一个图表示为G = (V, E)，其中V是指？（） A、一个点 B、一条边 C、边集合 D、点集合 答案：D 局部信息相似性链路预测的优势是什么？() A、精准 B、速度快 C、符合实际场景 D、包含节点属性 答案：B 下面哪个是全局信息预测算法？() A、Common neighBors (CN) B、JACCArD (JC) C、ADAmiC-ADAr (AA) D、PAgeRAnk 答案：D 谷歌搜索引擎的算法基本框架是？() A、Common neighBors (CN) B、JACCArD (JC) C、ADAmiC-ADAr (AA) D、PAgeRAnk 答案：D PAgeRAnk中，参数Oj是指() A、所有网页的数量 B、从网页引出去的链接的数量 C、指向网页的链接的数量 D、可调参数 答案：B 一个好的学习训练模型应该是？（） A、在训练时最小化错误率（提高在训练集上的准确率） B、模型应该简单（防止过拟合） C、将模型函数正则化 D、可以利用已知的数据特性，例如稀疏、低秩等 答案：ABCD 正则化是为了什么？
计算机导论 第1章计算机基础知识 教学目标 1.了解信息技术的相关概念 2.了解计算机的发展历程、特点、应用和分类 3.掌握计算机系统的组成（重点） 4.掌握信息在计算机中的表示形式（重点、难点） 第一节计算机概述 一、什么是计算机？ 计算机是一种能够接收和存储信息，并把存储在内部的程序对输入信息进行加工、处理，得到人们所期望的结果，然后把处理结果输出的高度自动化设备。 巴比奇在马洪发明的逻辑演示器的影响下，于1822年开始设计差分机（difference engine），其目标是能计算具有20位有效数字的6次多项式的值。这是第一台可自动进行数学变换的机器，因此他被称为“计算之父”。
计算理论的奠基人（图灵） ●Alan Turing（1912~1954）1936年上研究生时发表的一篇论文中提出了图灵机 （Turing Machine），奠定了计算机的理论基础。 ●第二次世界大战中，Turing 领导的小组制造出了破译德军 Enigma 密码的计算机，并成功地完成了任务。 ●Turing 与Church 合作给出了数学证明，断言未来计算机能 够象人那样具有思维能力（因而汉语中有了“电脑”）。 ●计算机学科的最高荣誉是ACM（美国计算机学会）图灵奖。 ●图灵测验： 一个人在不接触对象的情况下，进行一系列的提问，如果他根据这些回答无法 判断对象是人还是机器，则这种计算机具有与人相当 的智力。 世界上第一台电子数字计算机 ●1946年，在宾夕法尼亚大学Moore 学院， J. Eckert 和J. Mauchly 为实现弹道计算研制成功了 ENIAC（“电子数字积分计算机”，Electronic Numerical Integrator and Computer），它用了19000 个电子管， 重30 吨，耗电200 千瓦。 ●现在所谓的计算机就是电子数字计算机。 计算机体系结构的创始人（冯·诺依曼） ●1946年，John von Neumann（1903~1957）
形式语言与自动机理论试题答案解析 一、按要求完成下列填空 1.给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集（2x4'） (1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}} (2) {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}} 2.设∑={0,1},请给出∑上的下列语言的文法（2x5'） (1)所有包含子串01011的串 S→X01011Y X→ε|0X|1X Y→ε|0Y|1Y (2)所有既没有一对连续的0，也没有一对连续的1的串 A→ε|A’|A” A’→0|01|01A’ A”→1|10|10A” 3.构造识别下列语言的DFA 2x6' (1) {x|x∈{0，1}+且x以0开头以1结尾} （设置陷阱状态，当第一个字符为1时，进入陷阱状态） (2) {x|x∈{0，1}+且x的第十个字符为1} （设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态）
二、判断（正确的写T ，错误的写F ） 5x2' 1.设1R 和2R 是集合{a,b,c,d,e}上的二元关系，则 3231321)(R R R R R R R I I ? ( T ) 任取(x.,y),其中x,y },,,,{e d c b a ∈，使得321)(),(R R R y x I ∈。 )),(),((321R y z R R z x z ∈∧∈??I },,,,{e d c b a z ∈ )),(),(),((321R y z R z x R z x z ∈∧∈∧∈?? )),(),(()),(),((3231R y z R z x z R y z R z x z ∈∧∈?∧∈∧∈?? 3231),(),(R R y x R R y x ∈∧∈? 3231),(R R R R y x I ∈? 2.对于任一非空集合A ，Φ?A 2 ( T ) 3.文法G ：S A|AS A a|b|c|d|e|f|g 是RG ( F ) 4.3型语言 I 2型语言 I 1型语言 I 0型语言 ( F ) 5.s （rs+s ）*r=rr *s （rr *s ）* ( F ) 不成立，假设r,s 分别是表示语言R ，S 的正则表达式，例如当R={0}，S={1}, L(s(rs+s)*r)是以1开头的字符串，而L(rr*s(rr*s)*)是以0开头的字符串.L(s(rs+s)*r) ≠ L(rr*s(rr*s)*) 所以s(rs+s)*r ≠ rr*s(rr*s)*,结论不成立 三、设文法G 的产生式集如下，试给出句子aaabbbccc 的至少两个不同的推导（12分）。 aSBC aBC S |→ ab aB → bB →bb CB →BC bC →bc cC →cc
第三章作业答案 1．已知DFA M1与M2如图3－18所示。 (敖雪峰 02282068) (1) 请分别给出它们在处理字符串1011001的过程中经过的状态序列。 (2) 请给出它们的形式描述。 S q q 1 图3－18 两个不同的DFA 解答：(1)M1在处理1011001的过程中经过的状态序列为q 0q 3q 1q 3q 2q 3q 1q 3; M2在处理1011001的过程中经过的状态序列为q 0q 2q 3q 1q 3q 2q 3q 1; (2)考虑到用形式语言表示,用自然语言似乎不是那么容易,所以用图上作业法把它们用正则表达式来描述: M1: [01+(00+1)(11+0)][11+(10+0)(11+0)]* M2: (01+1+000){(01)*+[(001+11)(01+1+000)]*} ******************************************************************************* 2．构造下列语言的DFA ( 陶文婧 02282085 ) （1）{0，1}* ，1 （2）{0 ，1}+ ，1 （3）{x|x {0，1}+且x 中不含00的串} （设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）
（4）{ x|x∈{0，1}*且x中不含00的串} （可接受空字符串，所以初始状态也是接受状态） （5）{x|x∈{0，1}+且x中含形如10110的子串} （6）{x|x∈{0，1}+且x中不含形如10110的子串} （设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态） （7）{x|x∈{0，1}+且当把x看成二进制时，x模5和3同余，要求当x为0时，|x|=1,且x≠0时，x的首字符为1 } 1.以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入的符号为0，则进 入陷阱状态 2.设置7个状态：开始状态q s,q0:除以5余0的等价类，q1：除以5余1的等价类,q2:除以5 余2的等价类，q3:除以5余3的等价类，q4:除以5余4的等价类，接受状态q t
冯?诺依曼计算机的五个组成部分不包括（） A、运算器 B、控制器 C、处理器 D、存储器 答案：C 2、(单选，10分) 以下对强人工智能的描述不准确的是（） A、机器具有类人或者超越人的智慧 B、人脑与AI界限模糊 C、计算机可表现出不低于人类智能水平的外部智能行为 D、计算机与人类特征连结 答案：C 3、(单选，10分) 当前主流人工智能研究的三个重要特征不包括：（） A、关注智能体的外部行为，而不是产生该行为的内部过程 B、关注如何模拟人类纯粹智能活动，而不是脑力活动 C、将人工智能问题视为计算问题，通过数学建模进行求解 D、最终目标是得到能够适应人类生存环境的智能体 答案：C 4、(单选，10分) 以下哪个方法不属于检测人工智能的手段（） A、威诺格拉德模式挑战 B、机器的标准化测试 C、物理图灵测试 D、中国餐馆测试 答案：D 5、(单选，10分) 2016年3月15日，AlphaGo首次战胜的人类围棋世界冠军是：（） A、李世石 B、柯洁 C、古力 D、樊麾 答案：A
以下哪个部件不是AlphaGo的组成部分（） A、策略网络 B、评估网络 C、蒙特卡罗树搜算法 D、纳什均衡博弈算法 答案：D 7、(单选，10分) AlphaGo的评估网络的设计思想源于（） A、机器学习 B、增强学习 C、深度学习 D、无监督学习 答案：B 8、(单选，10分) AlphaGo的策略网络所采用的学习算法模型是（） A、深度卷积神经网络 B、循环神经网络 C、递归神经网络 D、深度博弈网络 答案：A 9、(单选，10分) 以AlphaGo为代表的智能博弈机器人是典型的强人工智能。 A、正确 B、错误 答案：B 10、(单选，10分) 图灵测试与人工智能研究的最终目标都是得到可以通过图灵测试的计算机。 A、正确 B、错误 答案：B
形式语言与自动机课后作业答案 第二章 4．找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。 答：G={N,T,P,S} 其中N={S,A,B,C,D} T={x,y} 其中x∈{所有字母} y∈{所有的字符} P如下: S→x S→xA A→y A→yB B→y B→yC C→y C→yD D→y 6．构造上下文无关文法能够产生 L={ω/ω∈{a,b}*且ω中a的个数是b的两倍} 答：G={N,T,P,S} 其中N={S} T={a,b} P如下: S→aab S→aba S→baa S→aabS S→aaSb S→aSab S→Saab S→abaS S→abSa S→aSba S→Saba S→baaS S→baSa S→bSaa S→Sbaa 7．找出由下列各组生成式产生的语言（起始符为S） (1)S→SaS S→b (2)S→aSb S→c (3)S→a S→aE E→aS 答：（1）b(ab)n /n≥0}或者L={(ba)n b/n≥0} (2) L={a n cb n /n≥0} (3)L={a2n+1 /n≥0} 第三章 1．下列集合是否为正则集，若是正则集写出其正则式。 （1）含有偶数个a和奇数个b的{a,b}*上的字符串集合 （2）含有相同个数a和b的字符串集合 （3）不含子串aba的{a,b}*上的字符串集合 答：（1）是正则集，自动机如下 (2) 不是正则集，用泵浦引理可以证明，具体见17题（2）。
(3) 是正则集 先看L’为包含子串aba的{a,b}*上的字符串集合 显然这是正则集，可以写出表达式和画出自动机。（略） 则不包含子串aba的{a,b}*上的字符串集合L是L’的非。 根据正则集的性质，L也是正则集。 4．对下列文法的生成式，找出其正则式 （1）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→abS A→bB B→b B→cC C→D D→bB D→d （2）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→cC A→bB B→bB B→a C→D C→abB D→d 答：(1) 由生成式得： S=aA+B ① A=abS+bB ② B=b+cC ③ C=D ④ D=d+bB ⑤ ③④⑤式化简消去CD，得到B=b+c(d+bB) 即B=cbB+cd+b =>B=(cb)*(cd+b) ⑥ 将②⑥代入① S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =>S=(aab)*(ab+ε)(cb)*(cd+b) (2) 由生成式得： S=aA+B ① A=bB+cC ② B=a+bB ③ C=D+abB ④ D=dB ⑤ 由③得 B=b*a ⑥ 将⑤⑥代入④ C=d+abb*a=d+ab+a ⑦ 将⑥⑦代入② A=b+a+c(d+b+a) ⑧ 将⑥⑧代入① S=a(b+a+c(d+ab+a))+b*a =ab+a+acd+acab+a+b*a 5.为下列正则集，构造右线性文法： (1){a,b}* (2)以abb结尾的由a和b组成的所有字符串的集合
计算智能概论 ——结课报告 通过一个学期的学习，我们对计算智能概论有了一个大概的了解，虽然我们还不能进行复杂的计算编程，但是对于基本概念我们还是有了初步的认识。遗传算法（Genetic Algorithm）是基于自然选择和基因遗传学原理的随机搜索算法。它是一种通过模拟自然进化过程搜索最优解的方法，遗传算法起源于对生物系统进行的计算机模拟研究。早在20 世纪40 年代，就有学者开始研究利用计算机进行生物模拟的技术，他们从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研究工作。早期的研究特点是侧重于对一些复杂操作的研究。最早意识到自然遗传算法可以转化为人工智能算法John H. Holland 教授。1965 年，Holland 教授首次提出了人工智能操作的重要性，并将其应用到自然系统和人工系统中。1967 年，Holland 教授的学生.J.D.Bagley 在其博士论文中首次提出了“遗传算法”一词，并发表了遗传算法应用方面的第一篇论文，从而创立了自适应遗传算法的概念e J.D.Bagley 发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用了双倍体的编码方法。 人工神经网络是由具有适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经。神经系统对真实世界物体所作出的交互反应。人工神经网络以其具有自学习、自组织、较好的容错性和。优良的非线性逼近能力，受到众多领域学者的关注。在实际应用中，80%～90%的人工神经网络模型是采。采用误差反传算法或其变化形式的网
络模型。 从生物神经元到人工神经网络:大脑与神经细胞、神经细胞与神经细胞构成了庞大天文数字量级的高度复杂的网络系统。也正是有了这样的复杂巨系统，大脑才能担负起人类认识世界和改造世界的任务。 “世界上最大的未开发疆域，是我们两耳之间的空间。”（美国汉诺威保险公司总裁比尔·奥伯莱恩） 1、生物神经系统和大脑的复杂性 生物系统是世界上最为复杂的系统。 生物神经系统活动和脑的功能，其复杂性是难以想象的。 ①人大脑平均只有3磅左右。只占身体重量比例的1/30； ②使眼睛可以辨别1000万种细微的颜色； ③使肌肉(如果全部向同一个方向运动)产生25吨的拉力； ④是由100亿个脑细胞和10兆个神经交汇丛组成。整个大脑的神经网络足足有10英里长。 人类的梦想重新构造人脑，并让其代替人类完成相应的工作。（无数科幻故事）智能是个体有目的的行为、合理的思维、以及有效的适应环境的综合能力；也可以说是个体认识客观事物和运用知识解决问题的能力。人类智能的具体含义：感知与认识客观事物、客观世界和自我的能力；通过学习获得经验、积累知识的能力；理解知识、运用知识和经验分析、解决问题的能力；联想、推理、判断、决策的能力；运用语言进行抽象、概括的能力；以上5点是人类智能的基本能力。 对以上5个基本问题的不同回答已经形成3个主要的学术流派：人工智
形式语言与自动机理论试题答案解析 一、按要求完成下列填空 1. 给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集 （2x4'） (1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}} (2) {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}} 2. 设∑={0,1},请给出∑上的下列语言的文法 （2x5'） (1)所有包含子串01011的串 S →X01011Y X →ε|0X|1X Y →ε|0Y|1Y (2)所有既没有一对连续的0，也没有一对连续的1的串 A →ε |A ’|A ” A’ →0|01|01A ’ A ” →1|10|10A ” 3. 构造识别下列语言的DFA 2x6' (1) {x|x ∈{0，1}+且x 以0开头以1结尾} （设置陷阱状态，当第一个字符为1时，进入陷阱状态） 1 S 1 1 0,10 (2) {x|x ∈{0，1} + 且x 的第十个字符为1} （设置一个陷阱状态，一旦发现x 的第十个字符为0，进入陷阱状态） 1S 0,1 0,10,10,10,110,0,10,10,10,1 0,1
二、判断（正确的写T ，错误的写F ） 5x2' 1.设1R 和2R 是集合{a,b,c,d,e}上的二元关系，则 3231321)(R R R R R R R ? ( T ) 任取(x.,y),其中x,y },,,,{e d c b a ∈，使得321)(),(R R R y x ∈。 )),(),((321R y z R R z x z ∈∧∈?? },,,,{e d c b a z ∈ )),(),(),((321R y z R z x R z x z ∈∧∈∧∈?? )),(),(()),(),((3231R y z R z x z R y z R z x z ∈∧∈?∧∈∧∈?? 3231),(),(R R y x R R y x ∈∧∈? 3231),(R R R R y x ∈? 2.对于任一非空集合A ，Φ?A 2 ( T ) 3.文法G ：S A|AS A a|b|c|d|e|f|g 是RG ( F ) 4.3型语言 2型语言 1型语言 0型语言 ( F ) 5.s （rs+s ）*r=rr *s （rr *s ）* ( F ) 不成立，假设r,s 分别是表示语言R ，S 的正则表达式，例如当R={0}，S={1}, L(s(rs+s)*r)是以1开头的字符串，而L(rr*s(rr*s)*)是以0开头的字符串.L(s(rs+s)*r) ≠ L(rr*s(rr*s)*) 所以s(rs+s)*r ≠ rr*s(rr*s)*,结论不成立 三、设文法G 的产生式集如下，试给出句子aaabbbccc 的至少两个不同的推导（12分）。 aSBC aBC S |→ ab aB → bB →bb CB →BC bC →bc cC →cc
形式语言与自动机的关系研究 新疆师范大学数理信息学院数学03-6班摘要： 形式语言的直观意义，自动机的直观意义，形式语言的定义， 形式语言的特征，语法的分类，自动机的定义，自动机的分 类，各种自动机的定义，形式语言和自动的的关系，自动机 的对语言的例子 基本关键词： 形式语言的定义；自动机的定义；形式语言和自动机的关系 1，形式语言的直观意义 α→的直观地讲，形式语言是用来精确描述语言和它结构的手段。它一重写规则β α,均为字符串。重写规则就是在包含α的字符穿中遇见规则左边的形式来表示，其中，β α时，α部分重新写为右边的β。这样一个初设的字符串通过不断地运用重写规则，就可以到另一个字符串。通过选择不同的规则并且以各种不同的顺序来运用最这些规则，如果指 定一个初始符，某规则以其为左部，一组规则就可以构成一个语法。 2，形式语言的定义
形式语法是一个四元组G=（N, V , P, S ）,其中N 是非终结符的有限集合，有时也称变量，它们相当于各种句法范畴。V 是终结符的有限集合，若语法生成的是自然语言，这些终端语符就相当于这种语言中具体的词，终端 语符集 这种语言的词库，P 是以重写规则的有限集合，基本形式P }{βα→，即""βα改写为，其中箭头表示指令，一条规则就是一个机械性的操作程序，用来演算它联系着的两侧语符集或语符序列之间的关系，而S 是一个特定的初始符； 3，语法的分类 乔姆斯在他的著名【文章】中根据重写规则将语法分成四类：正则语法，上下文有关语法，上下文无关语法；有这些语法生成的语言是正则语言，，上下文有关语言，上下文无关语言，递归数集合。 a 如果P 中的规则，满足如下的形式：x A Bx A →→或，，其中，A,B 是非终结符，x 是终结符，则G 称为正则语法（简称为FSG ）。 b 如果P 中的规则，满足如下的形式：α→A ,其中，A 是非终结符, α是由N 和V 中字符所组成的字符串（或可表示为()*∈V N α,*意味着它右边的字符可以重复0到任何 多次），则G 称为上下文无关语法（简称为CFG ）。 d 如果P 中的规则，满足如下的形式：αγββα→A ,其中，A 是非终结符,γβα,,,是字符串，且γ至少包含一个字符，则G 称为上下有无关语法（简称为CSG ）。 d 如果P 中的规则，满足如下的形式：其中，α，β是字符串，则G 称为无限制重写系统。 对于以上任何一种语法，两个字符串之间一次派生关系?可定义为： 如果y x →是P 中的规则，βαβαy x ?。 字符串α，β有多次派生关系* ?则是说，通过多次应用一次派生关系，从α可派生出β，并记为α* ?β： n αβαα==,0，而对n i i n i +?-=αα,1,....0。 给定以语法，其语言定义为所有合法终结字符串的集合。合法终结字符串是指由初始符S 出发，运用重写规则而派生得终结字符串，即， (){}ααα**;?∈=S V G L 例子：假设G=(N, V , P, S), N={S, A} , V={0, 1}, P={0,0,1→→→A A A A S } 则 ，{}110)(≥=m G L m 是正则语法，在V={0, 1}上它所对应的正则表达式是100*。 形式语言的特征： ⑴ 高度抽象化（采用形式化的手段，专用符号，数学公式来描述语言的，结构关系，这种关系是抽象的）。
一单选或填空题（10*3 = 30％） 1.下列叙述正确的是（） A.如果DFA不接受任何字符串，则该机器识别的语言为{ε}. B.如果DFA不接受任何字符串，则该机器识别的语言为φ. C.一个DFA可以没有起始状态. D.一个DFA的起始状态不能和接受状态相同. 2.下述（目前为止）肯定不正确的是（） A．NP NP? C.SAT是NP完全的 D.SAT是NP难的P? B. P 4.识别语言{0n1n|n ≥ 0}的文法为__________ 5.下述表达不正确的是（） A.所有的RL均是CFL B.所有的RL均是图灵可判定的 C.所有的CFL均是图灵可判定的 D.若语言A是图灵可判定的,则A和A不 全是图灵可识别的 6.背包问题:max: p1x1+p2x2+…+p n x n St: w1x1+w2x2+…w n x n A.若B 可判定，则A 也可判定 B.若B 可判定，则A 也不可判定 C.若B 不可识别,则A 也不可识别 D.A 和B 间的可判定性不存在任何关系 9.若图灵机的当前格局为uaq i bv ,其状态转移函数为),,(),(L c q b q j i =δ,则下一格局为_______. 10.若一个关系是自反,对称和传递的,则该关系为_____关系. 二 DFA 的形式描述为({q 1,q 2,q 3,q 4},{u,d}, δ, q 3,{ q 3}),其中δ在下表中给出.试. (13%) 三 S →AA | 0 A →SS | 1 四 给出产生语言A={a i b i c k | i ≥0, k ≥0}的上下文无关文法，并判断其是否歧 义.(10%) 五 证明：若A 和A 均为图灵可识别的，则A 为图灵可判定的.(10%) 六 判断下述公式的可满足性，并说明原因.(13%) (x ∨y)∧(x ∨y )∧(x ∨y) 七 令CONNECTED={ 一、选择题(每题1分，共15分) 1、人工智能是一门D A)数学和生理学B)心理学和生理学C)语言学 D)综合性的交叉学科和边缘学科 2、语义网络表达知识时，有向弧AKO链、ISA链是用来表达节点知识的（C）。 A)无悖性B)可扩充性C)继承性 3、(A->B)∧A=>B是C A)附加律B)拒收律C)假言推理 D)US 4、命题是可以判断真假的D A)祈使句B)疑问句C)感叹句 D)陈述句 5、仅个体变元被量化的谓词称为A A)一阶谓词B)原子公式C)二阶谓词 D)全称量词 6、MGU是A A)最一般合一B)最一般替换C)最一般谓词D)基替换 最一般合一 7、下列不在人工智能系统的知识包含的4个要素中D A)事实B)规则C)控制 D)关系 8、当前归结式是（）时，则定理得证。C A)永真式B包孕式（subsumed）C)空子句 9、或图通常称为D A）框架网络B)语义图C)博亦图D)状态图 10、不属于人工智能的学派是B A)符号主义B)机会主义C)行为主义 D)连接主义。 11、所谓不确定性推理就是从(A)的初始证据出发，通过运用()的知识，最终推出具有一定程度的不确定性但却是合理或者近乎合理的结论的思维过程。 A)不确定性,不确定性B)确定性,确定性 C)确定性,不确定性D)不确定性确定性 12.要想让机器具有智能，必须让机器具有知识。因此，在人工智能中有一个研究领域，主要研究计算机如何自动获取知识和技能，实现自我完善，这门研究分支学科叫（B）。A)专家系统B)机器学习C)神经网络D)模式识别 13、下列哪部分不是专家系统的组成部分（A） A.）用户B）综合数据库C）推理机 D）知识库 14、产生式系统的推理不包括（D） A）正向推理B）逆向推理C）双向推理D）简单推理 15、C(B|A)表示在规则A->B中，证据A为真的作用下结论B为真的B A)可信度B)信度C)信任增长度D)概率 二、填空题(每题1分，共30分) 1、人工智能的含义最早由一位科学家于1950年提出，并且同时提出一个机器智能的测试模型，请问这个科学家是图灵 2、从已知事实出发，通过规则库求得结论的产生式系统的推理方式是 正向推理。 3、AI的英文缩写是ArtificalIntelligence 。 4、不确定性类型按性质分：不确定性，模糊性， 不完全性，不一致性。 6、对证据的可信度CF（A）、CF（A1）、CF（A2）之间，规定如下关系： CF（~A）=、CF（A1∧A2）=、 CF（A1∨A2）=。-CF(A)，min{CF(A1),CF(A2)}，max{CF(A1),CF(A2)}) 7、图：指由节点和有向边组成的网络。按连接同一节点的各边的逻辑关系又可分为和或图与或图。 8、合一算法：求非空有限具有相同谓词名的原子公式集的MGU。 9、1997年５月，着名的“人机大战”，最终名为“深蓝”的计算机以3.5比2.5的总比分将世界国际象棋棋王卡斯帕罗夫击败。 10、人工智能的远期目标是制造智能机器，近期目标是实现机器智能。 三、简答及计算题(每题5分，共25分) . . 人工智能试卷四 一、选择题(每题1分，共15分) 1、AI的英文缩写是 A)Automatic Intelligence B)Artifical Intelligence C)Automatice Information D)Artifical Information 2、反演归结（消解）证明定理时，若当前归结式是（）时，则定理得证。 A)永真式B)包孕式（subsumed）C)空子句 3、从已知事实出发，通过规则库求得结论的产生式系统的推理方式是 A)正向推理B)反向推理C)双向推理 4、语义网络表达知识时，有向弧AKO 链、ISA 链是用来表达节点知识的（）。 A)无悖性B)可扩充性C)继承性 5、(A→B)∧A => B是 A)附加律B)拒收律C)假言推理D)US 6、命题是可以判断真假的 A)祈使句B)疑问句C)感叹句D)陈述句 7、仅个体变元被量化的谓词称为 A)一阶谓词B)原子公式C)二阶谓词D)全称量词 8、MGU是 A)最一般合一B)最一般替换C)最一般谓词D)基替换 9、1997年５月，著名的“人机大战”，最终计算机以3.5比2.5的总比分将世界国际象棋棋王卡斯帕罗夫击败，这台计算机被称为（） A）深蓝B）IBM C）深思D）蓝天 10、下列不在人工智能系统的知识包含的4个要素中 A)事实B)规则C)控制和元知识D)关系 11、谓词逻辑下，子句, C1=L∨C1‘, C2= ? L∨C2‘,若σ是互补文字的（最一般）合一置换，则其归结式C=（） A) C1’σ∨C2’σB)C1’∨C2’C)C1’σ∧C2’σD)C1’∧C2’ 12、或图通常称为 A）框架网络B)语义图C)博亦图D)状态图 13、不属于人工智能的学派是 A)符号主义B)机会主义C)行为主义D)连接主义。 14、人工智能的含义最早由一位科学家于1950年提出，并且同时提出一个机器智能的测试模型，请问这个科学家是 A)明斯基B).扎德C)图林D)冯.诺依曼 15.要想让机器具有智能，必须让机器具有知识。因此，在人工智能中有一个研究领域，主要研究计算机如何自动获取知识和技能，实现自我完善，这门研究分支学科叫（）。 A)专家系统B)机器学习C)神经网络D)模式识别 二、填空题(每空1.5分，共30分) 1、不确定性类型按性质分：随机性，模糊性，不完全性，不一致性。 2、在删除策略归结的过程中删除以下子句：含有的子句;含 有的子句;子句集中被别的子句的子句。 3、对证据的可信度CF（A）、CF（A1）、CF（A2）之间，规定如下关系： CF（~A）=、CF（A1∧A2 ）=、 CF（A1∨A2 ）= 4、图：指由和组成的网络。按连接同一节点的各边的逻辑关系又可分为和。 5、合一算法：求非空有限具有相同谓词名的原子公式集的 6、产生式系统的推理过程中，从可触发规则中选择一个规则来执行，被执行的规则称为。 7、P(B|A) 表示在规则中，证据A为真的作用下结论B为真的。 8、人工智能的远期目标是， 近期目标是。 三、简答及计算题(每题5分，共25分) 1、填写下面的三值逻辑表。 其中T，F，U分别表示真，假，不能判定 2、什么是产生式？产生式规则的语义是什么？ 答： 3、谓词公式G通过８个步骤所得的子句集合S，称为G的子句集。请写出这些步骤。 4、已知S={P(f(x),y,g(y)),P(f(x),z,g(x))}，求MGU 解： 5、证明G是否是F的逻辑结论； )) ( ) ( ( : )) ( ) ( ) ( ( : x Q x P x G x Q a Q x P x F ∧ ? ∨ ∧ ? 四、应用题(共30分) 1、用语义网络表示下列信息： (1)胡途是思源公司的经理，他35岁，住在飞天胡同68号 (2)清华大学与北京大学进行蓝球比赛，最后以89：102的比分结束。 答： 2、图示博弈树，其中末一行的数字为假设的估值，请利用α-β剪枝技术剪去不必要的分枝。（在节点及边上直接加注释） 3、设有如下关系：（1）如果x是y的父亲，y又是z的父亲，则x是z的祖父；（2）老李是大李的父亲；（3）大李是小李的父亲；问上述人员中谁和谁是祖孙关系？ 解： 答案： 一、1、B 2、C3、A4、C5、C 6、D 7、A 8、A 9、A10、D 11、A12、D13、B14、C 15、B 二、1、随机性，模糊性，不完全性，不一致性 2、纯文字，永真式，类含 福州大学2014～2015学年第2学期考试A卷 课程名称人工智能导论考试日期2015-6-14 考生姓名学号专业或类别 题号一二三四总分累分人 签名题分100 得分 考生注意事项：1、本试卷共8 页，请查看试卷中是否有缺页。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。 一、填空题(每空1分，共20分) 得分评卷人 1. 人工智能三大学派是、和。 2. 在知识表示方法中，与谓词逻辑表示为ISA（LIMING ，MAN）等效的语义网络形式 为。 3.状态空间表示法的两个基本概念是和。 4. 产生式系统由3个部分组成：一个总数据库、、。 5. ANN中文意义是。 6. 反向传播（back-propagation,BP）算法过程是从输出节点开始， ，所以称为“反向传播”。 7. 消解反演证明定理时，若当前归结式是，则定理得证。 8. 子句和P经过消解以后，得到。 9．基于规则的正向演绎系统，其规则形式为，其中前项要满足的条件是。 10. 语义网络下的推理是通过和实现的。 11. 被成为人工智能之父，曾提出一个机器智能的测试模型。 12. 谓词公式(?x)(?y)(?z)(P(x,y)∨Q(y,z)W(z))消去存在量词后，可以化为 。 13. 设E 1=P(a,v,f(g(y))),E 2 =P(z,f(a),f(u)),则E 1 和E 2 的mgu（最一般合一）为 。 14. 进化策略是在父矢量x i ，i=1,2,……p中，通过加入一个 变量以及预先选择x的标准偏差来产生子代矢量x。 二、选择题(每小题2分，共20分) 得分评卷人 1. 在图搜索中，选择最有希望的节点作为下一个要扩展的节点，这种搜索方法叫做( ) A. 宽度搜索 B. 深度搜索 C. 有序搜索 D. 广义搜索 2. 下列人工神经网络属于反馈网络的是（） A. Hopfield网 B. BP网络 C. 多层感知器 D. LVQ网络 3. 使用一组槽来描述事件的发生序列，这种知识表示法叫做( ) A. 语义网络法 B. 过程表示法 C. 剧本表示法 D. 框架表示法 4. 产生式系统的推理不包括( ) A. 正向推理 B. 逆向推理 C. 双向推理 D. 简单推理 5. 启发式搜索是寻求问题（）解的一种方法 A. 最优 B. 一般 C. 满意 D. 最坏 6. 语义网络表达知识时，有向弧AKO链、ISA链表达节点知识的（） A. 无悖性 B. 可扩充性 C. 继承性 D. 完整性 7. 下面表达式对中（）是能够合一的。 A. P（q（f（v）），g（u））和P（x，x） B. P（x，f（x））和P（y，y） C. P（y，y，B）和P（z，x，z） D. P（f（A），x），P（x，A） 8. 在遗传算法中，变量x的定义域为 [-2，5]，要求其精度为10-6，现用二进制进行编码，人工智能导论试卷
《人工智能导论》试卷
福州大学人工智能导论试卷
相关主题
文本预览