- 1、本文档共16页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
练习
1.1 图给出两台DFA M1和M2的状态图. 回答下述有关问题.
M1的起始状态是q1
M1的接受状态集是{q2}
M2的起始状态是q1
M2的接受状态集是{q1,q4}
对输入aabb,M1经过的状态序列是q1,q2,q3,q1,q1
M1接受字符串aabb吗?否
M2接受字符串ε吗?是
1.2 给出练习2.1中画出的机器M1和M2的形式描述.
M1=(Q1,Σ,δ1,q1,F1) 其中
Q1={q1,q2,q3,};
Σ={a,b};
δ1为:
a b q1
q2
q3 q2 q1
q3 q3
q2 q1 q1是起始状态
F1={q2}
M2=(Q2,Σ,δ2,q2,F2) 其中
Q2={q1,q2,q3,q4};
Σ={a,b};
3)δ2为:
a b q1
q2
q3
q4 q1 q2
q3 q4
q2 q1
q3 q4 q2是起始状态
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,且要求符合规定的状态数。
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,Σ,δ,q0,F},F={ri1,……,rik}.添加一个状态p后,ri1,……,rik分别向p引ε箭头,将ri1,……,rik变为非接受状态,p变为接受状态。又因为添加ε箭头不影响NFA识别语言,所以命题成立。
2.14 a 证明:设M是一台语言B的DFA,交换M的接状态与非接受状态得到一台新的DFA,则这台新的DFA是识别B 的补集,因此,正则语言类受在补运算下封闭。
b 举例说明:设M是一台识别语言B的NFA,交换M的接受状态与非接受状态得到一台新的NFA,这台新的NFA不一定识别B的补集。NFA识别的语言类在补集下封闭吗?解释你的回答。
解:
M是DFA, M是{Q,∑,δ,q0,F},令N={Q,∑,δ,q0,Q-F},设ω=ω1ω2…ωn是字母表上任意字符串,因为M与N均为DFA,所以必然存在Q中状态序列r0,r1,…,rn,使得:r0=q0, δ(ri, ωi+1)=ri+1, i=0,…,n-1
1)若rn(F 则ω(B;
2)若rn(F,则rn(Q-F,即N接受ω,若ω(B,
所以N接受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=(Q1,Σ,δ1,q1,F1)识别A1。如下构造N=(Q1,Σ,δ1,q1,F1)。N应该识别A1*。
N的状态集是N1的状态集。
N的起始状态是N1的起始状态相同。
F={q1}∪F1。F的接受状态是原来的接受状态加上它的起始状态。
定义δ如下:对每一个q属于
文档评论(0)