有哪些信誉好的足球投注网站- 1、本文档共6页，可阅读全部内容。
- 2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
查看更多
第4章 词法分析
1.构造下列正规式相应的DFA.
（１） 1(0|1) *101
答案：
1) 先构造NFA：
2)将NFA 确定化:
∑
Q 0 1 [X] X [A] A [A] A [A] A [A,B] B [A,B] B [A,C] C [A,B] B [A,C] C [A] A [A,B,Y] Y [A,B,Y] Y [A,C] C [A,B] B 3) DFA:
2. 已知NFA＝（｛x,y,z｝,{0,1},M,{x},{z}），其中：M(x,0)={z}，M(y,0)={x,y}，,M(z,0)={x,z}，
M(x,1)={x}，M(y,1)=φ，M(z,1)={y}，构造相应的DFA。
答案：
根据题中映射，得如下NFA转换矩阵：
0 1 x z x y x,y z x,z y 转成NFA（这步可省）：
确定化：
∑ Q 0 1 [x] X [z] A [x] X [z] [A] [x,z] B [y] C [x,z] [B] [x,z] B [x,y] E [y] C [x,y] E [x,y] E [x,y,z] F [x] X [x,y,z] [F] [x,y,z] F [x,y] E
4. 将下图的（a）和（b）分别确定化和最小化：
确定化：
∑ Q a b [0] [0] [0,1] 1 [1] 2 [0,1] [1] [0,1] 1 [1] 2 [1] 2 [0] 0
最小化：
(0( {0,1} {2}
因为：{0,1}a={1} {0,1}b={2} 不能拆分
(1( {0,1} {2}
0,1二状态合并，得
因为自动机（b）已确定化，所以只做最小化：
(0( {1,2,3,4,5} {0}
因为 {4}a={0} {1,2,3,5}a={1,2,3, 5}
(1( {1,2,3,5} {4} {0}
因为{1,5}b={4} {2,3}b={2,3}
(2( {1, 5} {2,3} {4} {0}
因为 {2}a={1} {3}a={3}
(3( {1, 5} {2} {3} {4} {0}
因为 {1, 5}a={1,5} {1, 5}b={4} 不能拆分
(4( {1, 5} {2} {3} {4} {0}
将 {1, 5}合并得：
5.构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串：每个1 都有0 直接跟在
右边。并给出该语言的正规式。
答案：
1)按题意相应的正规表达式可为(0 | 10)*， 构造相应的DFA：
2)将DFA转成右线性文法：
S-〉A|ε
A-0A|0|1B
B-0A|0
8.给出下述文法所对应的正规式：
S→0A|1B
A→1S|1
B→0S|0
答案：
将A、B 产生式的右部代入S 中,得：
S=01S|01|10S|10=（01|10）S| 01|10
所以：S= (01|10)* |01|10
10.构造下述文法G[S]的自动机：
S-A0
A-A0|S1|0
该自动机是确定的吗？若不确定，则对它确定化。该自动机相应的语言是什么？
答案：
将题中左线性文法转换为自动机：
因为是左线性文法，要增加一开始状态X，开始符号S成终结状态：
该自动机为NFA，确定化：
∑ Q 0 1 [x] X [A] A [A] A [A,S] B [A,S] [B] [A,S] B [A] A
该自动机表达的语言用正规式表示为：00(0|10)*， 或：
以00开头，0结尾，中间若有1，则1后一定跟0。
附加题：
已有NFA M=（{S，A，B，F}，{0,1},f,{S},{F}）,状态图如下图所示，
1． 将此NFA转化成规范DFA；
2． 转化成正规文法。
3. 列出它拒绝接受的2个字符串（不同字符开头）
答案：
确定化：
∑
Q 0 1 [S] S [A,F] A [A,F] [A] [A,F] A [A,B] B [A,B] B [A,F] A [A,B,F] C [A,B,F] [C] [A,F] A [A,B,F] C
此DFA已为最小化的DFA
转化成右线性的正规文法
S-0A|0
A-0A|0|1B
B-0A|0|1C|1
C-0A|0|1C|1
列出它拒
文档评论（0）