二、判断(正确的写T,错误的写F) 5x2'
1.设R1和R2是集合{a,b,c,d,e}上的二元关系,则( T )
任取(x.,y),其中x,y {a,b,c,d,e},使得(x,y) (R1 R2)R3。 z((x,z) R1 R2 (z,y) R3) z {a,b,c,d,e} z((x,z) R1 (x,z) R2 (z,y) R3)
z((x,z) R1 (z,y) R3) z((x,z) R2 (z,y) R3) (x,y) R1R3 (x,y) R2R3 (x,y) R1R3 R2R3
2.对于任一非空集合A,Φ 2 ( T ) 3.文法G:S A|AS A a|b|c|d|e|f|g 是RG ( F ) 4.3型语言
2型语言
1型语言
0型语言 ( F )
A
(R R)R RR RR1231323
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分)。 S aBC|aSBC
aB ab
bB→bb CB→BC bC→bc cC→cc
推导一: S=>aSBC
=>aaSBCBC
=>aaaBCBCBC =>aaabCBCBC =>aaabBCCBC =>aaabbCCBC =>aaabbCBCC
年 月 日 《形式语言与自动机理论》试题一、 二、 三、 试述正规文法、有穷自动机的概念,相互之间的关系作用。 试述上下文无关文法、下推自动机的概念,相互...
形式语言与自动机试题(A卷)_理学_高等教育_教育专区。清华大学本科生考试试题... 形式语言与自动机试题 2页 免费 形式语言与自动机理论试... 3页 免费 形式...
形式语言与自动机理论试题一、按要求完成下列填空 1. 给出集合{Φ ,{Φ }}和集合{ε ,0,00}的幂集 2. 设∑={0,1},请给出∑上的下列语言的文法 (1...
形式语言与自动机理论试题答案解析_计算机硬件及网络_IT/计算机_专业资料。形式语言与自动机理论试题答案解析一、按要求完成下列填空 1. 给出集合{Φ ,{Φ }}和...
形式语言与自动机理论-蒋宗礼-第二章参考答案_工学_高等教育_教育专区。形式...题参见下题: 11、给定 RG G1 = (V1 , T1 , P , S1 ) 1 G2 = ...
形式语言与自动机考题2012_计算机硬件及网络_IT/计算机_专业资料。西安交大形式... 形式语言与自动机试卷 3页 2下载券 形式语言与自动机理论试... 6页 免费 ...
电子科技大学 博士学位论文 形式语言与自动机理论若干问题研究 姓名:陈文宇 申请学位级别:博士 专业:计算机应用技术 指导教师:孙世新 20091125 摘要 摘要 计算理论是...
形式语言与自动机理论-蒋宗礼-第三章参考答案_工学_高等教育_教育专区。形式...( M 1 ) 注:转化成相应的 DFA 进行处理,然后可参考第 8 题的思路 证明:...
形式语言与自动机理论试题 3页 免费 形式语言与自动机理论-04 50页 2财富值 形式语言与自动机理论-03 33页 2财富值喜欢此文档的还喜欢 形式语言与自动机理论...
形式语言与自动机理论-蒋宗礼-第四章参考答案_工学_高等教育_教育专区。形式...题 (L1∪{ε })*=L1*其中 L1 为正则语言 又 r 为正则表达式 正则语言...
热门文档