＋

1.5.12 有语言L={w|w∈(0,1），并且w中至少有两个1，又在任何两个1之间有偶数个0，试构造接受该语言的确定有限状态自动机（DFA）。

1.5.13 已知正规式(1)((a|b)*|aa)*b和正规式(2)(a|b)*b。 (1)试用有限自动机的等价性证明正规式(1)和(2)是等价的。 (2）给出相应的正规文法。

1.5.14 某操作系统下合法的文件名为device:name.extension,其中第一部分（device:）和第三部分（.extension)可缺省，若device, name和extension都是字母串，长度不限，但至少为1，画出识别这种文件名的确定有限自动机。

1.5.15 Pascal语言无符号数的正规定义如下： Num→digit+(.digit+)?(E(+|-)?digit+)?

其中digit表示数字，用状态转换图表示接受无符号数的确定有限自动机。

1.5.16 在C语言中无符号整数可用十进制（非0打头）、八进制（0打头）和十六进(0X打头）表示，试写出其相应的文法和识别无符号数的DFA(假定位数不限)。

1.5.17 下列程序段若以B表示循环体，A表示初始化，I表示增量，T表示测试。 I:=1；

while I<=n do begin

sun:=sun+a[I];

I:=I+l End

请用正规表达式表示这个程序段可能的执行序列。

1.5.18 在操作系统的进程管理中，进程的状态转换如图2.50所示。假设现有两个进程Pi和CPU每次只能运行一个进程。当P1、P2都处于就绪状态时为初态，当P1、P2都处于睡眠状态时为终态。请用一个有限自动机来描述这个进程管理系统。

图2.50 进程状态转换图

1.5.19 有一台自动售货机，接收1分和2分硬币，出售3分钱一块的硬糖。顾客每次向机器中

投放≥3分的硬币，便可得到一块糖（注意：只给一块并且不找钱）。 (1)写出售货机售糖的正规表达式。 (2)构造识别上述正规式的最简DFA。

1.5.20 证明：一不含无用状态的有限自动机M的接收集L(M)是无限集，当且仅当M相应的状态转换图中含有回路。

1.5.21 假定A和B都是正规集，请用正规集与有限自动机的等价性说明A∪B也是正规的。

1.5.22 下面的正规式等价吗？为什么？ (1)(a|b)* (2) (a*|b*)* (3)((ε|a)b*)*

1.5.23 （电子科大1996年研究生试题） 构造识别下列单词符号的状态转换图：

begin end标识符正整数＋－***，．∷＝

1.5.24 （清华大学1998年研究生试题） 请将图2.57所示的有穷自动机M1最小化。

图2.57 有穷自动机M1

1.5.25 （清华大学1998年研究生试题） 将有穷自动机M2确定化

M2=({U,V,W,X}，10,1｝,f,{U}，{W}） 其中：f(U,0）＝φ f(U,1）＝｛V,X} f(V,0)={V} f(V,l）＝tvlwl f(W,0)={X｝ f(W,1)＝{W} f(X,0)={X} f(X,1）＝{X}

1.5.26 （清华大学1998年研究生试题） 将图2.58所示的DFA最小化。

图2.58 DFA

1.5.27 （中科院计算所1997年研究生试题） 为正规式(a|b) *a(a|b)构造一个确定的有限自动机。

1.5.28 （南开大学1998年研究生试题） 写出正规式(alb) *(aa|bb)(a|b)*的DFA。

1.5.29 （复旦大学1999年研究生试题）

将图2.59所示的非确定有限自动机(NFA)变换成等价的确定有限自动机(DFA)。

图2.59 NFA

其中，X为初态，Y为终态。

1.5.30 （上海交大1997年研究生试题）

请构造与正规式R=(a*|b*)b(ba)*等价且状态最少的DFA。

1.5.31 （国防科大1999年研究生试题）

构造一个确定的有限自动机DFA,它接受∑＝{0,1}上的所有不带前导0的二进制区数。

1.5.32 （国防科大2000年研究生试题）

已知DFA M如图2.60所示。

图2.60 DFA M

请给出M所识别的字的全体L(M)。

1.5.33 （华中理工2001年研究生试题）

构造一个确定的有穷自动机DFA M,它识别∑={a,b}上所有满足如下条件的字符串：字 符串由a, b组成，且其中b的个数为3k (k≥0)。

1.5.34 （华中理工2001年研究生试题）

正规式(ab）*a与正规式a(ba) * 是否等价？请说明理由。

1.5.35 DFA与NFA有何区别

5

※<习题三>

第三章 语法分析

典型例题: 单项选择题

3.1.1. 文法G: S-xSxly所识别的语言是_____（陕西省1997年自考题） a. xyx b. (xyx)* c. xnyxn(n≥0) d. x*yx* 3.1.2. 文法G描述的语言L(G)是指_____。

a. L(G)=｛α|S=>α，α ∈VT*｝b. L(G)={ α|SA=>α,α ∈VT*｝

c．L(G)={ α|S=>α，α∈(VT∪VN)*｝d. L(G)=｛α|S=>α,α∈(VT∪VN)*｝ 3.1.3. 有限状态自动机能识别＿。

a.上下文无关文法 b.上下文有关文法 c.正规文法 d.短语文法

3.1.4. 设G为算符优先文法，G的任意终结符对a, b有以下关系成立____。 a.若f(a)>g(b)，则a>b b.若f(a)

3.1.5．茹果文法G是无二义的，则它的任何句子α_＿。（西电1999年研究生试题） a.最左推导和最右推导对应的语法树必定相同 b.最左推导和最右推导对应的语法树可能不同 c.最左推导和最右推导必定相同

d.可能存在两个不同的最左推导，但它们对应的语法树相同