西理工编译原理试题集1-7(6)

现给出一个NFA: M=(Σ，Q，0，{9}，δ)

其中Σ=,羊，空，菜，狼}，Q={0，1，2，3，4，5，6，7，8，9}，转形函数： δ(0，羊)=1，δ(1，空)=2，δ(2，菜)=3，δ(2，狼)=5 δ(3，羊)=4，δ(5，羊)=6，δ(4，狼)=7，δ(6，菜)=7 δ(7，空)=8，δ(8，羊)=9

4 C语言无符号实数用正则表达式怎么定义？ 答：

digit ?0 ?1 ?... ?9 digits ?digit(digit)* fraction ? . digits

exponent ?E (+ ?- ??) digits )

num ? digits ( fraction | ? ) (exponent | ? ) 5. 分析下面各正规表达式所表示的语言。 (1) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)*

答：(1) ,α|α∈{0，1}*，α中有偶数个0和偶数个1}，即由偶数个0和偶数个1构成的串。

6. 何谓扫描器？扫描器的功能是什么？

答：扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析，识别出一个个的单词符号，其输出结果是单词符号，供语法分析器使用。

一般把词法分析器安排成一个子程序，每当语法分析器需要一个单词符号时就调用这个子程序。每一次调用，词法分析器就从输入串中识别出一个单词符号，把它交给语法分析器。 词法分析器工作的第一步是输入源程序文本。输入串中一般都包含一些没有意义的字符，如：空白符、跳格符、回车符和换行符等编辑性字符除了出现在文字常数中之外，在别处的任何出现都没有意义，而注解部分几乎允许出现在程序中的任何地方。它们不是程序的必要组成部分，预处理时可以将其剔掉。词法分析器一般会构造一个预处理子程序来处理上述任务。

7. 试简述有穷状态自动机与正则表达式的等价性概念。

答：．∑上的非确定有限自动机M所能识别字的全体L(M)是∑上的一个正规集；同时，对于∑上的每个正规集V，存在一个∑上的确定有限自动机M，使得V=L(M)。

六、应用题：

1. 有一个语言，它接收Σ=,0，1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。

（１）给出该语言的正规式 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化 解法1：

（１）按题意相应的正规表达式是0*(0 | 10)*0*或0*( 100*)*0*。 （２）构造NFA为 0*的NFA为：

? ? 0 ? ?

0 | 10的NFA为：

? ? 1 0 ? 0 ? ?

(0 | 10)*的NFA为：

? ? ? ? 0 ? ? ? 1 ? 0 ?

0*(0 | 10)*0*的NFA为（给各个结点标上序号）

? ? 0 1 ? ? ? 0 2 ? 3 ? 4 5 ? ? 6 1 9 10 0 7 ? 11 ? 0 ? 8 ? 12 ? 13 ? ? ? 14 15 ? 0 16 ? 17

（３）用子集法确定化 I I0 I1 {0，1，3，4，5，——————————————————————{2，7，16}={1，2，3，4，5，6，9，13，14，15，{10}6，9，13，14，15，17} 17}∪{5，7，8，9，13，14，15，17}∪{15，16，17}＝={10，11} {1，2，3，4，5，6，7，8，9，13，14，15，16，17} {1，2，3，4，5，————————————————{2，7，16}，同上 6，7，8，9，13，14，15，16，17} {10，11} ————————————{10}同上 ? {12}＝{5，6，8，9，12，13，14，15，17} {5，6，8，9，12，——————————————————{7，16}＝{5，6，7，8，9，13，14，15，16，17} {10}旧13，14，15，17} 态 {5，6，7，8，9，————————————{7，16}旧态 13，14，15，16，17}

令：{0，1，3，4，5，6，9，13，14，15，17}＝A； {1，2，3，4，5，6，7，8，9，13，14，15，16，17}＝B； {10，11}＝C；

——————{10}旧态 {5，6，8，9，12，13，14，15，17}＝D； {5，6，7，8，9，13，14，15，16，17}＝E； 画出DFA如图所示： 0 0 A 1 B 1 C 0 1 1 D 0 0 E

（４）对该DFA进行状态最小化

?＝{I(1)，I(2)}＝{{C}，{A，B，D，E}} I(1)＝{C}不可再分； 看I(2)＝{A，B，D，E}：

{A，B，D，E}0＝{B，E}，落入了I(2)； {A，B，D，E}1＝{C}，落入了I(1)；

所以，{A，B，D，E}是等价状态，不再分；

因此，从{A，B，D，E}中抽取一个状态作为代表，C不变，得到简化了的DFA如图所示：

0 1 A C 0

解法2：

（２）构造NFA为

0 0 0 ε X 0 ε 1 1 1 0 2 ε 3 ε Y

（3）用子集法确定化 I I0 I1 S 0 1 {X，0，1，3，Y} {0，1，3，Y} {2} 1 2 3 {0，1，3，Y} {2} {1，3，Y} DFA为： 0 0 1 0 1 0 D {0，1，3，Y} {2} 2 2 3 {1，3，Y} {1，3，Y} / 3 4 {2} 4 4 3 A 1 C B

（４）可最小化，终态组为{A，B，D}，非终态组为{C}； {A，B，D}0?{A，B，D}， {A，B，D}1?{C}，

所以A，B，D为等价状态，可合并。

0 1 A C 0