《编译原理》期中及期末习题

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.可能存在两个不同的最左推导,但它们对应的语法树相同

联系客服:779662525#qq.com(#替换为@)