编译原理 第2章习题课

1.构造正规式的DFA。

（1）1(0|1)*101

首先构造NFA：

NFA化为DFA：

状态转换表：

状态转换图：

初态

化简后得：

（2）(a|b)*(aa|bb)(a|b)*

？

NFA化为DFA：

所以，DFA为：

化简得：

（3）（0|11*0）*

NFA到DFA：

化简后得；

2.将下图确定化和最小化。

a

a

0 1

a,b

解: 首先取A=ε-CLOSURE({0})={0}, NFA确定化后的状态矩阵为:

NFA确定化后的DFA为：

a

a

A B

a

b b

C

将A,B 合并得:

a b

A C

a

3.构造一个DFA，它接受∑={0，1}上所有满足如下条件的字符串，每个1都有0直接跟在后边。

解：按题意相应的正规表达式是0*(0 | 10)*0*

构造相应的DFA，首先构造NFA为

0 0 0

ε ε ε ε Y

1 0

用子集法确定化

DFA为

0

1 0 2

1 1 0

1

4

0

4.给出NFA等价的正规式R。

方法一：首先将状态图转化为

ε 1 1 ε 消去 得

0,1

ε 11 ε 消去其余结点

、 0，1

（0|1）*11

NFA等价的正规式为（0|1）*11

方法二：NFA→右线性文法→正规式

A→0A|1A|1B

B→1C

C→ε

A=0A+1A+1B

B=1

A=0A+1A+11

A=(0+1)*11→(0|1)*11

5.试证明正规式（a|b）*与正规式（a*|b*）*是等价的。

证明：

(1)

正规式(a|b)*的NFA为 => ε ε

b

a

其最简DFA为

=>

b

(2)正规式（a*|b*）*的 NFA为：

a

其最简化DFA为：

a

εε

=> X ε ε =>

εε b

b

DFA的状态转换表：

由于这两个正规式的最小DFA相同，所以正规式(a|b)*等价于正规式(a*|b*)*。

6.设字母表∑={a,b},给出∑上的正规式R=b*ab(b|ab)*。

（1） 试构造状态最小化的DFA M，使得L（M）=L（R）。

（2） 求右线性文法G，使L（G）=L（M）。

解: (1)构造NFA:

(2)将其化为DFA,转换矩阵为:

再将其最小化得:

（2）对应的右线性文法G=（{X,W,Y},{a,b},P,X）

P: X→aW|bX W→bY|b y→aW|bY|b

文法G[〈单词〉]为：

〈单词〉-〉〈标识符〉|〈整数〉

〈标识符〉-〉〈标识符〉〈字母〉|〈标识符〉〈数字〉|〈字母〉

〈整数〉-〉〈数字〉|〈整数〉〈数字〉

〈字母〉-〉A|B|C

〈数字〉|->1|2|3

（1）改写文法G为G’，使L(G’)=L(G)。

（2）给出相应的有穷自动机。

解：（1）令D代表单词，I代表标识符，Z代表整数，有G’（D）：

D→I | Z

I→A | B | C | IA | IB | IC | I1 | I2 | I3

Z→1 | 2 | 3 | Z1 | Z2 | Z3

(2) 左线性文法G’所对应的有穷自动机为：

M=({S,D,I,Z},{1,2,3,A,B,C},f,S,{D})

f: f(S,A)=I, f(S,B)=I, f(S,C)=I

f(S,1)=Z f(S,2)=Z f(S,3)=Z

f(I,A)=I f(I,B)=I f(I,C)=I

f(I,1)=I f(I,2)=I f(I,3)=I f(I, ε)=I

f(Z,1)=Z f(Z,2)=Z f(Z,3)=Z f(Z, ε)=D

给出下述文法所对应的正规式。

S→0A|1B

A→1S|1

B→0S|0

解: 相应的正规式方程组为：

S=0A+1B ①

A=1S+1 ②

B=0S+0 ③

将②，③代入①，得

S=01S+01+10S+10 ④

对④使用求解规则，得 (01|10)* （01|10）为所求。

给出文法G[S]，构造相应最小的DFA。

S->aS|bA|b

A-> aS

方法一：

S=aS+bA+b

A=aS

S=aS+baS+b S=(a+ba)*b

即：S=(a|ba)*b

正规式(a|ba)*b对应的NFA：

正规式(a|ba)*b对应的DFA：

化简后：

方法二：P43 右线性正规文法到有穷自动机的转换。

文法S->aS|bA|b

A-> aS

对应的NFA为：

M=({S,A,D},{a,b},f,{S},{D})

其中：f (S,a)=S, f(S,b)=A, f(S,b)=D, f(A,a)=S

其NFA图为：

a

S b A

a

b

D

NFA确定化后的状态矩阵为:

NFA确定化后的DFA为：

a b

1 2

a

给出下述文法所对应的正规式：

S->aA

A->bA+aB+b

B->aA

解：将文法改为：

S=aA ①

A=bA+aB+b ②

B=aA ③

将③代入②，得

A=bA+aaA+b ④ 将④用求解规则，得

A= (b|aa)*b ⑤,带入①得，S= a(b|aa)*b,

故文法所对应的正规式为R= a(b|aa)*b。

给出与下图等价的正规文法G。

a

A a B b C

b a b

D

b

答: 该有穷自动机为:

M=({A,B,C,D},{a,b},f,{A},{C,D})

其中f(A,a)=B, f(A,b)=D, f(B,a)=φ, f(B,b)=C,

f(C,a)=A, f(C,b)=D, f(D,a)=B, f(D,b)=D

根据其转换规则，与其等价的正规文法G为

G=（{A,B,C,D},{a,b},P,A）,其中

P : A→aB|bD B→bC C→aA|bD|ε D→aB|bD|ε

.解释下列术语和概念：

(1)确定有穷自动机

答：一个确定有穷自动机M是一个五元组M=（Q，Σ，f，S，Z），

其中：

Q是一个有穷状态集合，每一个元素称为一个状态；

Σ是一个有穷输入字母表，每个元素称为一个输入字符；

f是一个从Q*Σ到Q的单值映射；

f（qi,a）=qj (qi,qj∈Q,a∈Σ)

表示当前状态为qi，输入字符为a时，自动机将转换到下一个状态qj,qj称为 qi 的一个后继状态。我们说状态转换函数是单值函数，是指 f（qi,a） 惟一地确定了下一个要转移的状态，即每个状态的所有输出边上标记的输入字符不同。

S∈Q，是惟一的一个初态；

Z 真包含于Q，是一个终态集。

（2）非确定有穷自动机

一个非确定有穷自动机M是一个五元组M=（Q，Σ，f，S，Z），其中：

Q是一个有穷状态集合，每一个元素称为一个状态；

Σ是一个有穷输入字母表，每个元素称为一个输入字符；

状态转换函数是一个多值函数。

f（qi,a）={某些状态的集合}(qi∈Q)，表示不能由当前状态、当前输入字符惟一地确定下一个要转移的状态，即允许同一个状态对同一输入字符有不同的输出边。

S 包含于 A，是非空初态集。

Z 真包含于 Q，是一个终态集。

（3）正规式和正规集

有字母表Σ={a1,a2,…an}，在字母表Σ上的正规式和它所表示的正规集可用如下规则来定义：

（1）φ是Σ是的正规式，它所表示的正规集是φ，即空集{}。

（2）ε是Σ上的正规式，它所表示的正规集仅含一空符号串，即 {ε} 。

（3）是Σ上的一个正规式，它所表示的正规集是由单个符号ai 所组成，即{ai}。

（4）e1和e2是Σ是的正规式，它们所表示的正规集分别为L(e1)和L(e2),则

①e1 | e2是Σ上的一个正规式，它所表示的正规集为

L(e1 | e2)=L(e1)∪L(e2).

② e1e2是Σ上的一个正规式，它所表示的正规集为

L(e1e2)=L(e1)L(e2).

③ (e1)*是Σ上的一个正规式，它所表示的正规集为

L((e1)*)=L((e1))*.

3．1构造下列正规式相应的DFA。

(1) 1 ( 0 | 1)*101

(2) ( a | b )*( aa | bb )( a | b )*

(3) (( 0 | 1 )* | ( 11 ))*

(4) ( 0 | 11*0 )*

3．2将下面图(a)和(b)分别确定化和最小化.

a

a

0 1

a,b

(a)

b b a

0 2 b 3

a

a a

a b b a

1 4 5

b

（b）

构造一个DFA，他接收∑={0，1}上所有满足如下条件的字符串，每个1都有0直接跟在右边。

给出文法G[S]，构造相应最小的DFA。

S aS | bA | b

A aS

给出下述文法所对应的正规式：

S->Aa

A->bA+aB+b

B->aA

给出与下图等价的正规文法G。

a

A a B b C

b a b

D

b

给出与图中的NFA等价的正规式R。

文法G[〈单词〉]为：

〈单词〉 〈标识符〉| 〈整数〉

〈标识符〉 〈标识符〉〈字母〉| 〈标识符〉〈数字〉|〈字母〉

〈整数〉 〈数字〉|〈整数〉〈数字〉

〈字母〉 A | B | C

〈数字〉 1 | 2 | 3

（1） 改写文法G为G’，使L(G’)=L(G).

（2） 给出相应的有穷自动机。

试证明正规式（a|b）*与正规式（a*|b*）*是等价的。

3．10给出下述文法所对应的正规式：

S 0A | 1B

A 1S | 1

B 0S | 0

3．11设字母表Σ={a,b}，给出Σ上的正规式R=b*ab(b | ab)*.

(1) 试构造状态最小化的DFA M，使得L（M）=L（R）。

(2) 求右线性文法G，使L（G）=L（M）。

3．12解释下列术语和概念。

（1） 确定有穷自动机

（2） 非确定有穷自动机

（3） 正规式和正规集

本文来源：https://www.2haoxitong.net/k/doc/645ab029aff8941ea76e58fafab069dc5122477d.html