形式语言与自动机理论-蒋宗礼-第三章参考答案

第三章作业答案

1．已知DFA M1与M2如图3－18所示。 (敖雪峰 02282068)

(1) 请分别给出它们在处理字符串1011001的过程中经过的状态序列。 (2) 请给出它们的形式描述。

S

q q

1

图3－18 两个不同的DFA

解答：(1)M1在处理1011001的过程中经过的状态序列为q 0q 3q 1q 3q 2q 3q 1q 3; M2在处理1011001的过程中经过的状态序列为q 0q 2q 3q 1q 3q 2q 3q 1;

(2)考虑到用形式语言表示,用自然语言似乎不是那么容易,所以用图上作业法把它们用正则表达式来描述:

M1: [01+(00+1)(11+0)][11+(10+0)(11+0)]*

M2: (01+1+000){(01)*+[(001+11)(01+1+000)]*}

******************************************************************************* 2．构造下列语言的DFA

( 陶文婧 02282085 ) （1）{0，1}*

，1

（2）{0，

1}

+

，1

（3）{x|x {0，1}+且x 中不含00的串}

（设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）

（4）{ x|x∈{0，1}*且x中不含00的串}

（可接受空字符串，所以初始状态也是接受状态）

（5）{x|x∈{0，1}+且x中含形如10110的子串}

（6）{x|x∈{0，1}+且x中不含形如10110的子串}

（设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）

（7）{x|x∈{0，1}+且当把x看成二进制时，x模5和3同余，要求当x为0时，|x|=1,且x≠0时，x的首字符为1 }

1.以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入的符号为0，则进

入陷阱状态

2.设置7个状态：开始状态q s,q0:除以5余0的等价类，q1：除以5余1的等价类,q2:除以5

余2的等价类，q3:除以5余3的等价类，q4:除以5余4的等价类，接受状态q t

（8）{x|x∈{0，1}+且x的第十个字符为1}

（设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态）

（9）{x|x∈{0，1}+且x以0开头以1结尾}

（设置陷阱状态，当第一个字符为1时，进入陷阱状态）

（10）{x|x∈{0，1}+且x中至少含有两个1}

（11）{x|x ∈{0，1}+且如果x 以1结尾，则它的长度为偶数；如果x 以0结尾，则它的长度

为奇数}

可将{0，1}+的字符串分为4个等价类。 q 0： [ε]的等价类，对应的状态为终止状态 q 1:x 的长度为奇且以0结尾的等价类 q 2：x 的长度为奇且以1结尾的等价类 q 3: x 的长度为偶且以0结尾的等价类 q 4: x 的长度为偶且以1结尾的等价类

（12）{x|x 是十进制非负数}

5，

6，7，8，9

4，9

（13）Φ

（14）ε

*******************************************************************************

3 (1) （张友坤02282061）

∑={0,1}

Set(q0)={x | x∈∑* }

(2)

∑={0,1}

Set(q0)=ε

Set(q1)={x | x∈∑+ }

（3）

∑={0,1}

Set(q0)= ε

Set(q1)={x | x∈∑+并且x中不含形如00的子串}

Set(q2)={x | x∈∑+并且x中不含形如00的子串}

(4)

∑={0,1}

Set(q0)={x | x∈∑*并且x中不含形如00的子串}

Set(q1)={x | x∈∑*并且x中不含形如00的子串}

(5)

∑={0,1}

Set(q0)= {x | x∈∑*,并且x∈{0}*或者x中含形如100的子串}

Set(q1)={x | x∈∑*,并且x中含形如1的子串}

Set(q2)={x | x∈∑*,并且x中含形如10的子串}

Set(q3)={x | x∈∑*,并且x中含形如101的子串}

Set(q4)={x | x∈∑*,并且x中含形如1011的子串}

Set(q5)={x | x∈∑*,并且x中含形如10110的子串}

(6)

∑={0,1}

Set(q0)= {ε}

Set(q1)={x | x∈{0+}}

Set(q2)={x | x∈∑*,并且x中不含形如10110的子串而且x中含有1} Set(q3)={x | x∈∑*,并且x中不含形如10110的子串而且x中含有1} (7)

∑={0,1}

Set(qs)= {ε}

Set(qe)= {0}

Set(q1)={x | x∈∑+,并且把x看成二进制数时，x% 5=1}

Set(q2)={x | x∈∑+,并且把x看成二进制数时，x% 5=2}

Set(q3)={x | x∈∑+,并且把x看成二进制数时，x% 5=3}

Set(q4)={x | x∈∑+,并且把x看成二进制数时，x% 5=4}

Set(q0)={x | x∈∑+,并且把x看成二进制数时，x% 5=0并且x不为0} (8)

M={Q, ∑,δ,q0,F}

Q={q0,q1,q2, (10)

∑={0,1}

当0<=i<=8时候，

δ(q i,0)= δ( q i,1)=q（i+1）

δ( q 9,1)=q10

δ(q 10,0)= δ( q 10,1)=q10

F={ q 10}

Set(q0)= {ε}

Set(q1)= {0,1}

Set(q2)={x | x∈∑+,并且|x|=2}

Set(q3)={x | x∈∑+,并且|x|=3}

Set(q4)={x | x∈∑+,并且|x|=4}

Set(q5)={x | x∈∑+,并且|x|=5}

Set(q6)={x | x∈∑+,并且|x|=6}

Set(q7)={x | x∈∑+,并且|x|=7}

Set(q8)={x | x∈∑+,并且|x|=8}

Set(q9)={x | x∈∑+,并且|x|=9}

Set(q10)={x | x∈∑+,并且x的第十个字符是1}

(9) M={Q, ∑,δ,q0,F}

Q={q0,q1,q2 }

∑={0,1}

δ(q 0,0)=q1

δ(q 1,0)= q1

δ(q 1,1)= q2

δ(q 2,1)= q2

δ(q 2,0)= q1

F={ q 2}

Set(q0)= {ε}

Set(q1)={x | x∈∑+,并且x以0开头以0结尾}

Set(q2)={x | x∈∑+,并且x以0开头以1结尾}

(10) M={Q, ∑,δ,q0,F}

Q={q0,q1,q2 }

∑={0,1}

δ(q 0,0)=q0

δ(q 0,1)=q1

δ(q 1,0)= q1

δ(q 1,1)= q2

δ(q 2,1)= q2

δ(q 2,0)= q2

F={ q 2}

Set(q0)= {0}*

Set(q1)={x | x∈∑+,并且x中只有一个1 } Set(q2)={x | x∈∑+,并且x至少有俩个1} (11) M={Q, ∑,δ,q0,F}

Q={q0,q1,q2 , q3,q4 }

∑={0,1}

δ(q 0,0)=q1

δ(q 0,1)=q4

δ(q 1,0)= q3

δ(q 1,1)= q2

δ(q 2,1)= q4

δ(q 2,0)= q1

δ(q 3,0)= q1

δ(q 3,1)= q4

δ(q 4,1)= q2

δ(q 4,0)= q3

F={ q 0 ,q 1 ,q 2}

Set(q0)= {ε}

Set(q1)={x | x∈∑+,以0结尾，长度为奇数} Set(q2)={x | x∈∑+,以1结尾，长度为偶数} Set(q3)={x | x∈∑+,以0结尾，长度为偶数} Set(q4)={x | x∈∑+,以1结尾，长度为奇数} (12)

M={Q, ∑,δ,q0,F}

Q={q0,q1,q2,q3,q4}

∑={.,0,1,2, (9)

F={q1,q2,q4}

δ(q 0,0)=q1

δ(q 0,1|2|3|4|5|6|7|8|9)=q2

δ(q 1, . )=q2

δ(q 2,0|1|2|3|4|5|6|7|8|9)=q2

δ(q 2, . )=q3

δ(q 3,0|1|2|3|4|5|6|7|8|9)=q4

δ(q 4,0|1|2|3|4|5|6|7|8|9)=q4

Set(q0)= {ε}

Set(q1)={0 }

Set(q2)={十进制正整数}

Set(q3)={十进制非负整数后面接个小数点. }

Set(q4)={十进制正小数}

（13）

Set(q0)= {ε} Set(q0)=? （14）

Set(q0)= {ε}

******************************************************************************* 4 在例3-6中，状态采用]...[21n a a a q 的形式，它比较清楚地表达出该状态所对应的记忆内

容，给我们解决此问题带来了很大的方便，我们是否可以直接用]...[21n a a a 代替

]...[21n a a a q 呢？如果能，为什么？如果不能，又是为什么？从此问题的讨论，你能总

结出什么来？ （唐明珠 02282084） 答：我认为能够直接用]...[21n a a a 代替]...[21n a a a q ，因为在例3-6中，]...[21n a a a q 只是一种新的表示方法，用来表示状态存储的字符，这样就省去了在δ中逐一给出每一个具体

的输入字符和状态的定义。它的作用在于使FA 中状态定义更加简洁。 得到结论：在今后描述FA 时，应该根据具体的情况，使用适当的方法。

******************************************************************************* 5．试区别FA 中的陷阱状态和不可达状态。 （吴贤珺 02282047） 解：⑴ 陷阱状态（课本97页）：指在其它状态下发现输入串不可能是该FA 所识别的句子

时所进入的状态。FA 一旦进入该状态，就无法离开，并在此状态下，读完输入串中剩余的字符。

⑵ 不可达状态（课本108页）：指从FA 的开始状态出发，不可能到达的状态。就FA

的状态转移图来说，就是不存在从开始状态对应的顶点出发，到达该状态对应顶点的路径。

⑶ 从两者的定义可见：相对于不可达状态来说，陷阱状态是可达的。但是，它们都是

状态转移图中的非正常状态。如果从状态转移图中的状态引一条弧到不可达状态，同时不可达状态所有的移动都是到自身。这样，不可达状态就变成了陷阱状态。

****************************************************************************** 注：此题目有问题，可以将题设改为：x 中0和1个数相等且交替出现

6．证明：题目有不严密之处，图中给出DFA 与题目中的语言L （M ）={x|x x ∈{0，1}+ 且x 中0的个数和1的个数相等}不完全对应，首先图中的DFA 可接受空字符串，而L （M ）不接受，其次，对于有些句子，例如1100，L （M ）可以接受，但DFA 不接受 （1）根据图中的DFA 可看出，右下角的状态为陷阱状态，所以去除陷阱状态 （2）由DFA 可构造出与其对应的右线性文法： （刘钰 02282083）

01|110|0

00,0101|0110|10

S A A S S B

B S S A S S B S S S S →→→→→→→→将1S,1代入；代入得

由此可以看出该文法接受的语言为L={(10|01)*

},显然01或10分别是作为整体出现的，

所以L(M)中0和1的个数相等。

****************************************************************************** 7．设DFA M=),,,,(0F q Q δ∑，证明：对于∑

=∈∈

?)),,((),(,,,*

y x q xy q Q q y x δδδ

注：采用归纳证明的思路

证明： (周期律 02282067) 首先对y 归纳，对任意x 来说，|y| = 0时，即y=ε

根据DFA 定义,),(q q =εδ)),,(()),,((),(),(y x q x q x q xy q δδεδδδδ===,故原式成立。

当|y| = n 时，假设原式成立，故当|y|= n+1时， 不妨设y = wa, |w| = n, |a| = 1

根据DFA 定义∑∈=a a x q xa q ),),,((),(δδδ，故

)

),,(()),,(()),),,((()),,((),(),(y x q wa x q a w x q a xw q xwa q xy q δδδδδδδδδδδ=====原式成立，

同理可证，对任意的y 来说，结论也是成立的。 综上所述，原式得证

******************************************************************************* 8．证明:对于任意的DFA M 1=(Q,Σ,δ,q 0,F 1) 存在DFA M 2=(Q,Σ,δ,q 0,F 2), （冯蕊 02282075）

使得L(M 2)=Σ*—L （M 1）。 证明：（1）构造M 2。 设DFA M 1=(Q,Σ,δ,q 0,F 1) 取DFA M 2=(Q,Σ,δ,q 0,Q —F 1) （2）证明L(M 2)=Σ*—L （M 1） 对任意x ∈Σ*

x ∈ L(M 2)=Σ*—L （M 1）?δ(q,x)∈Q —F 1?δ（q,x ）∈Q 并且δ（q,x ）?F 1?x ∈Σ*并且x ?L(M 1)?x ∈Σ*—L （M 1）

******************************************************************************* 9. 对于任意的DFA M 1=(Q 1,∑,δ1,q 01,F 1),请构造DFA M 1=(Q 2,∑,δ2,q 02,F 2)，使得

L(M 1)=L(M 2)T 。其中L(M)T ={x|x T ∈L(M)} （褚颖娜 02282072） (1) 构造ε-NFA M 使得 L(M)=L(M 1) 取ε-NFA M=( Q,∑,δ, q 0,{ q 01}) 其中:

1) Q= Q 1∪{ q 0}, q 0? Q 1

2) 对于? q,p ∈Q 1,a ∈∑,如果δ1(q,a)=p,q ∈δ(p,a) 3) δ(q 0,ε)= F 1 (2) 证明：L(M)=L(M 1)T

对? x=a 1 a 2… a m ∈L(M)

q 0 a 1 a 2… a m ├q f a 1 a 2… a m ├a 1 q 1 a 2… a m ├a 1 a 2 q 2… a m ├…├a 1 a 2…q m-1a m ├a 1 a 2…a m q 01

其中q f ∈δ(q 0,ε), q 1∈δ(q f , a 1), q 2∈δ(q 1, a 2),…q 01∈δ(q m-1, a m ) 并且q f ∈F 1 则δ1(q 01, a m )= q m-1, δ1(q m-1, a m-1)= q m-2,…δ1(q 2, a 2)= q 1δ1(q 1, a 1)= q f 因此q 01 a m a m-1…a 1├a m q m-1 a m-1…a 1├a m a m-1…q 2 a 2 a 1├a m a m-1… a 2 q 1a 1 ├a m a m-1… a 2 a 1q f

因此a m a m-1…a 1∈L(M 1) 即 x T ∈L(M 1)

同理可证对于? x=a 1 a 2… a m ∈L(M 1) x T=a m a m-1…a 1∈L(M 1) L(M)=L(M 1)T 得证

（3）将ε-NFA M 确定化

首先构造与ε-NFA M=( Q,∑,δ, q 0,{ q 01}) 等价的NFA M 3=( Q,∑,δ2, q 0,{ q 01}) 其中对于?（q,a ）∈Q*∑ δ2(q,a)=δ^ (q,a)

然后按照以前学过的方法构造与NFA M 3=( Q,∑,δ2, q 0,{ q 01})等价的DFA

M 1=(Q 1,∑,δ1,[q 0],F 1) 其中：Q 1=2Q F 1={ q 01}

δ1([q 1,q 2 ,… ,q n ],a)=[p 1,p 2 ,…,p n ] 当且仅当δ2({q 1,q 2 ,… ,q n },a)={ p 1,p 2 ,…,p n }

******************************************************************************* 注：此题（10题）张友坤、吴玉涵所做完全一样！！

10、构造识别下列语言的NFA （吴玉涵02282091）

(1){{0,1}00}x x x +∈且中不含形如的子串

(2){{0,1}10110}x x x +

∈且中含形如的子串

(3){{0,1}}x x x +∈且中不含形如10110的子串

(4){{0,1}10101}x x x +∈和的倒数第个字符是，且以结尾

1

(5){{0,1}01}x x x +∈且以开头以结尾

(6){{0,1}}x x x +∈且中至少含有两个1

0，1

*(7){{0,1}}

x x x ∈且如果以1结尾，则它的长度为偶数； 如果以0结尾，则它的长度为奇数

(8){{0,1}}x x x +∈且的首字符和尾字符相等

(9){,{0,1}}T x x x ωω+∈

这是最基本的单元，其他的可以通过这个逐级构造出来，以满足题目要求。

*******************************************************************************11.根据给定的NFA ，构造与之等价的DFA. （吴丹 02282090）

解答：

图3-9所示NFA等价的DFA （2）NFA M的状态转移函数如表3-10

**************************************************************************** 12．证明对于任意的NFA ，存在与之等价的NFA,该NFA 最多只有一个终止状态

（刘钰 02282083） 证明：对于任意的NFA M=(Q ，∑，δ，q0，F) ，我们如果能构造出一个只有一个终止状态的NFA ，并且与之等价，即可证明上面的定理 而对于任意的NFA 存在下面两种情况： (1)终止状态只有一个 (2)终止状态有多个

要构造这个等价的NFA,可以采用如下方法： 对(1)无需变化，该NFA 即为满足条件的NFA

对(2)可以在该NFA 的状态图上添加一个新的终止状态，并将原来的多个终止状态所连接的弧复制到该状态上，此时这个终止状态为新状态图中唯一的终止状态，且这个新的NFA 与原 NFA 等价，满足条件 我们总能构造出这样的NFA

因此对于任意的NFA ，存在与之等价的NFA,该NFA 最多只有一个终止状态

******************************************************************************* 13．试给出一个构造方法，对于任意的NFA ),,,,(10111F q Q M δ∑=，构造NFA

=2M ),,,,(2022F q Q δ∑，使得)()(1*2M L M L -=∑

注：转化成相应的DFA 进行处理，然后可参考第8题的思路

证明： (周期律 02282067)

首先构造一个与NFA 1M 等价的DFA ，3M 根据定理3.1（P106），)()(13M L M L =

构造),],[,,,(30333F q Q M δ∑=其中

∑

∈?≠?==a Q p p p F p p p Q p p p p p p F Q m m m m Q ,}...,{},}...,{,}...,{|]...,{[,2211212121331φ

}...{)},...({]...[)],...([111113m n m n p p a q q p p a q q =?=δδ

在此基础上2M ，,,3232δδ==Q Q }]...[|]...{[3112φ==F p p p p F m m 即取所有1M 确定化后不是终结状态的状态为2M 的终结状态。 为了证明)()(3*

2M L M L -=

∑

，我们在3M 的基础上=4M ),,,,(4044F q Q δ∑，其

中,,3434δδ==Q Q 44Q F =，即所有1M 确定化后的状态都为终结状态。显然

,)(*4∑=M L

),(2M L x ∈?则φδ≠20),(F x q ),(),(330M L x F x q ??≠?φδ 又因为

∈?∈?∈),(),(),(04030x q F x q Q x q δδδ,)(*4∑=M L 故∈x )(3*M L -∑，

故)()(3*

2M L M L -?

∑

同理容易证明)()(3*

2M L M L -?∑

故)()(3*

2M L M L -=

∑

，又因为)()(13M L M L =，故)()(1*2M L M L -=∑

可知，构造的2M 是符合要求的。

******************************************************************************* 14．构造识别下列语言的ε-NFA 。 (吴贤珺 02282047)

⑴ { x │x ∈{0,1}+ 且x 中含形如10110的子串 }∪{ x │x ∈{0,1}+

和x 的倒数第10

个字符是1，且以01结尾 }。

解：得到的ε-NFA 如下所示：

⑵ { x │x ∈{0,1}+

且x 中含形如10110的子串 }{ x │x ∈{0,1}+

和x 的倒数第10个字符是1，且以01结尾 } 解：得到的ε-NFA 如下所示：

⑶ { x │x ∈{0,1}+

且x 中不含形如10110的子串 }∪{ x │x ∈{0,1}+

且x 以0开头以1

结尾 }。

解：关键是构造第一个FA ，方法是设置5个状态：

q 0：表示开始状态，以及连续出现了两个以上的0时所进入的状态。

q 1: 表示q 0状态下接受到1时（即开始状态或2个以上的0后输入1时）所进入

的状态。

q 2: 表示q 1状态下接受到0时（即开始状态或2个以上的0后输入10时）所进入

的状态。

q 3: 表示q 2状态下接受到1时（即开始状态或2个以上的0后输入101时）所进入

的状态。

q 4: 表示q 3状态下接受到1时（即开始状态或2个以上的0后输入1011时）所进

入的状态。

故得到的ε-NFA 如下所示：

⑷ { x│x∈{0,1}+ 且x中不含形如00的子串 }{ x│x∈{0,1}+ 且x中不含形如11的

子串 }。

解：得到的ε-NFA如下所示：

另外，本题可以构造DFA如下（其中q t为陷阱状态）：

⑸ { x │x ∈{0,1}+ 且x 中不含形如00的子串 }∩{ x │x ∈{0,1}+

且x 中不含形如11的子

串 }。

解：由于x 中既不含形如00的子串，又不含形如11的子串，故x 中只能是01相间的

串。所以，得到的ε-NFA 如下所示：

另外，本题可以构造DFA 如下（其中q +为陷阱状态）：

*******************************************************************************

15．（1）根据NFAM 3的状态转移函数，起始状态q 0的ε闭包为 ε-CLOSURE （q 0）={ q 0, q 2}。

q 0={ q 0, q 2}，q 1={ q 0, q 1，q 2}，q 2={ q 0, q 1，q 2，q 3}，因为q 3为终止状态，所以q 2={ q

0, q 1，q 2，q 3}为终止状态

2

（2）又上述方法得

0=1,31=3，22=0,1，2，33=0,1，34=1，2，3

有终止状态，所以q0, q1，q2，q3,q4均为终止状态

注：本题没有必要按照NFA到DFA转化的方法来做，而且从ε-NFA到NFA转化时状态没有必要改变，可以完全采用ε-NFA中的状态

如（1）

******************************************************************************* 16.证明对于?的FA M1=(Q1,∑1,δ1,q01,F1)，FA M1=(Q2,∑2,δ2,q02,F2)，存在FA M，

使得L(M)= L(M1)∪L(M2) （褚颖娜02282072）

证明：不妨设Q1 与Q2的交集为空

（1）构造M=（Q1∪Q2∪{ q0},∑,δ, q0,F）其中：

1）∑=∑1∪∑2 F= F1∪F2

编译原理课后习题答案(第三版)

精品文档 第二章 P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法： E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ?+?+?+?+?+?+?+?+??????+?+?+?+?+?+********()*()*()*()*()*()*() 最右推导: E E T E T F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树：/********************************

《形式语言与自动机》(王柏、杨娟编著)课后习题答案

形式语言与自动机课后习题答案 第二章 4．找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。 答：G={N,T,P,S} 其中N={S,A,B,C,D} T={x,y} 其中x ∈{所有字母} y ∈{所有的字符} P 如下: S →x S →xA A →y A →yB B →y B →y C C →y C →y D D →y 6．构造上下文无关文法能够产生 L={ω/ω∈{a,b}*且ω中a 的个数是b 的两倍} ! 答：G={N,T,P,S} 其中N={S} T={a,b} P 如下: S →aab S →aba S →baa S →aabS S →aaSb S →aSab S →Saab S →abaS S →abSa S →aSba S →Saba S →baaS S →baSa S →bSaa S →Sbaa 7．找出由下列各组生成式产生的语言（起始符为S ） (1) S →SaS S →b (2) S →aSb S →c (3) / (4) S →a S →aE E →aS 答：（1）b(ab)n /n ≥0}或者L={(ba)n b /n ≥0} (2) L={a n cb n /n ≥0} (3) L={a 2n+1 /n ≥0} 第三章 1． 下列集合是否为正则集，若是正则集写出其正则式。 （1） 含有偶数个a 和奇数个b 的{a,b}*上的字符串集合 （2） 含有相同个数a 和b 的字符串集合 （3） < （4） 不含子串aba 的{a,b}*上的字符串集合 答：（1）是正则集，自动机如下 a

a (2) 不是正则集，用泵浦引理可以证明，具体见17题（2）。 (3) 是正则集 先看L’为包含子串aba的{a,b}*上的字符串集合 { 显然这是正则集，可以写出表达式和画出自动机。（略）则不包含子串aba的{a,b}*上的字符串集合L是L’的非。 根据正则集的性质，L也是正则集。 4．对下列文法的生成式，找出其正则式 （1）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→abS A→bB B→b B→cC C→D D→bB … D→d （2）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→cC A→bB B→bB B→a C→D C→abB D→d 答：(1) 由生成式得： S=aA+B ① A=abS+bB ② ] B=b+cC ③ C=D ④ D=d+bB ⑤ ③④⑤式化简消去CD，得到B=b+c(d+bB) 即B=cbB+cd+b =>B=(cb)*(cd+b) ⑥ 将②⑥代入① S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =>S=(aab)*(ab+ε)(cb)*(cd+b) (2) 由生成式得： S=aA+B ① A=bB+cC ② … B=a+bB ③ C=D+abB ④ D=dB ⑤ 由③得B=b*a ⑥

(完整版)编译原理课后习题答案

第一章 1．典型的编译程序在逻辑功能上由哪几部分组成？ 答：编译程序主要由以下几个部分组成：词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、错误处理、表格管理。 2. 实现编译程序的主要方法有哪些？ 答：主要有：转换法、移植法、自展法、自动生成法。 3. 将用户使用高级语言编写的程序翻译为可直接执行的机器语言程序有哪几种主要的方式？ 答：编译法、解释法。 4. 编译方式和解释方式的根本区别是什么？ 答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执行，所以编译方式的效率高，执行速度快； 解释方式：在执行时，必须源程序和解释程序同时参与才能运行，其不产生可执行程序文件，效率低，执行速度慢。

第二章 1.乔姆斯基文法体系中将文法分为哪几类？文法的分类同程序设计语言的设计与实现关 系如何？ 答：1）0型文法、1型文法、2型文法、3型文法。 2） 2. 写一个文法，使其语言是偶整数的集合，每个偶整数不以0为前导。 答： Z→SME | B S→1|2|3|4|5|6|7|8|9 M→ε | D | MD D→0|S B→2|4|6|8 E→0|B 3. 设文法G为： N→ D|ND D→ 0|1|2|3|4|5|6|7|8|9 请给出句子123、301和75431的最右推导和最左推导。 答：N?ND?N3?ND3?N23?D23?123 N?ND?NDD?DDD?1DD?12D?123 N?ND?N1?ND1?N01?D01?301 N?ND?NDD?DDD?3DD?30D?301 N?ND?N1?ND1?N31?ND31?N431?ND431?N5431?D5431?75431 N?ND?NDD?NDDD?NDDDD?DDDDD?7DDDD?75DDD?754DD?7543D?75431 4. 证明文法S→iSeS|iS| i是二义性文法。 答：对于句型iiSeS存在两个不同的最左推导： S?iSeS?iiSes S?iS?iiSeS 所以该文法是二义性文法。 5. 给出描述下面语言的上下文无关文法。 （1）L1={a n b n c i |n>=1,i>=0 } （2）L2={a i b j|j>=i>=1} （3）L3={a n b m c m d n |m,n>=0} 答： （1）S→AB A→aAb | ab B→cB | ε （2）S→ASb |ab

[军事理论]各章节答案

中国国防与历代军事思想 34 我国贯彻积极防御的军事战略方针。T 46 中国的古代军事思想成熟于下列的哪个时期？(D) A. 唐朝 B. 汉朝 C. 西周 D. 春秋战国 49 世界最早的管形火器长竹杆火器和突火枪发明于下面哪个朝代？(B) A. 北宋 B. 南宋 C. 元朝 D. 明朝 52 《孙子兵法》提出"不战而屈人之兵"的战略思想，并提出"兵者，以?为植，以文为种； 武为表，文为里"的治国思想。（ F ） 54 提出“天下虽安，忘战必危”的战备观的，是：C A. 孙子 B. 吴子 C. 田穰苴 D. 尉缭子 81 毛泽东军事思想的核心是：B A. 军事辩证法 B. 人民战争思想 C. 人民军队思想 D. 人民战争的战略战术 85 我军的基本作战方针是：(C) A. 击溃战 B. 消耗战 C. 歼灭战 D. 阵地战 歼灭战就是歼灭敌人一切有生力量。（ F ）[保存自己，消灭敌人] 87 毛泽东认为，发生战争的根本原因是：(D) A. 霸权主义 B. 帝国主义 C. 政治冲突 D. 私有制与阶级的出现 87 战争的性质和结局受什么决定？A (最后一行） A. 政治 B. 军事 C. 经济 D. 国防实力 93 研究和指导战争必须着眼于战争的什么差异？BCD A. 规模 B. 地域 C. 性质 D. 时间 95 100 正义战争是人民战争，人民战争也一定是正义战争。错 (人民战争必然是正义战争，正义战争不一定是人民战争） -------世界军事领域正在发生的军事技术革命的核心是：(A) A.信息技术 B. 综合集成技术 C. 多军兵种合成 D. 新作战思想 --------国家利益包括：（ABCD ） A 领土主权完整B政治制度C文化传统D国民经济 人的主观能动性是战争胜负的决定因素之一。T 西周时期的军事思想奠定了中国古代军事思想的根基。T 第六章精确制导技术 159 惯性制导系统是不断修正导弹的加速度，从而攻击目标。F 测量加速度，修正轨道161自主式/惯性制导的导弹一经发射，就与发射点及目标点无关，而只与导弹本身有关。T 对于地形匹配制导，导弹飞经地域之地形越复杂，制导精度就越高。（T ） 对于地形匹配制导的导弹，地形越复杂，则制导精度越高。T 地形匹配制导的精度与射程有关而与地形无关.F 162 精确制导武器利用ＧＰＳ系统可以大大提高制导精度。T GPS制导有以下特点：ABC A. 命中精度高 B. 制导距离远 C. 发射后不管 D. 抗干扰能力强 163 某地对空导弹可能采用的制导方式是：C A. 自主式制导 B. 惯性制导 C. 无线电指令制导 D. 天文制导 某导弹采用遥控制导，则此导弹可能是: （ABD ） A、空对空导弹 B、空对地导弹 C、地对地导弹 D、地对空导弹

形式语言与自动机理论试题答案解析

形式语言与自动机理论试题答案解析 一、按要求完成下列填空 1.给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集（2x4'） (1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}} (2) {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}} 2.设∑={0,1},请给出∑上的下列语言的文法（2x5'） (1)所有包含子串01011的串 S→X01011Y X→ε|0X|1X Y→ε|0Y|1Y (2)所有既没有一对连续的0，也没有一对连续的1的串 A→ε|A’|A” A’→0|01|01A’ A”→1|10|10A” 3.构造识别下列语言的DFA 2x6' (1) {x|x∈{0，1}+且x以0开头以1结尾} （设置陷阱状态，当第一个字符为1时，进入陷阱状态） (2) {x|x∈{0，1}+且x的第十个字符为1} （设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态）

二、判断（正确的写T ，错误的写F ） 5x2' 1.设1R 和2R 是集合{a,b,c,d,e}上的二元关系，则 3231321)(R R R R R R R I I ? ( T ) 任取(x.,y),其中x,y },,,,{e d c b a ∈，使得321)(),(R R R y x I ∈。 )),(),((321R y z R R z x z ∈∧∈??I },,,,{e d c b a z ∈ )),(),(),((321R y z R z x R z x z ∈∧∈∧∈?? )),(),(()),(),((3231R y z R z x z R y z R z x z ∈∧∈?∧∈∧∈?? 3231),(),(R R y x R R y x ∈∧∈? 3231),(R R R R y x I ∈? 2.对于任一非空集合A ，Φ?A 2 ( T ) 3.文法G ：S A|AS A a|b|c|d|e|f|g 是RG ( F ) 4.3型语言 I 2型语言 I 1型语言 I 0型语言 ( F ) 5.s （rs+s ）*r=rr *s （rr *s ）* ( F ) 不成立，假设r,s 分别是表示语言R ，S 的正则表达式，例如当R={0}，S={1}, L(s(rs+s)*r)是以1开头的字符串，而L(rr*s(rr*s)*)是以0开头的字符串.L(s(rs+s)*r) ≠ L(rr*s(rr*s)*) 所以s(rs+s)*r ≠ rr*s(rr*s)*,结论不成立 三、设文法G 的产生式集如下，试给出句子aaabbbccc 的至少两个不同的推导（12分）。 aSBC aBC S |→ ab aB → bB →bb CB →BC bC →bc cC →cc

形式语言与自动机

形式语言与自动机的发展和在计算理论中的作用 2015060104020王桢 形式语言是语言学衍生过来的，开始形式语言并没有用于研究计算机编程语言，而只是研究自然语言的结构。在电子计算机出现以后，人们就马上想到用计算机来作自然语言的机械翻译。可是这项工作并没有所成果，对自然语言的结构 理解太片面化，翻译质量不理想也很难提高。1956年，乔姆斯基发表了用形 式语言方法研究自然语言的第一篇文章。他对语言进行定义：给定一组符号，称 为字母表，用∑表示。又用∑*表示∑中字母组成的所有符号串的集合。∑*的每个子集都是∑上的一个语言。乔姆斯基的语言定义方法为人们所公认，一直沿用下来，乔姆斯基根据文法将语言分成3大类。同时克林在研究神经细跑中，建立 了识别语言的系统有穷状态自动机。乔姆斯基发现自动机和文法分别从生成和识别去表达语言，并建立了形式文法和自动机之间的联系，证明语言的形式文法与自动机之间存在着如下的对应关系：①若某一语言能用图灵机来识别，则它就能 用O型文法生成，反之亦然；②若某一语言能用线性有界自动机来识别，则它 就能用上下文敏感文法生成，反之亦然；③若某一语言能用后进先出自动机来识别，则它就能用上下文自由文法生成，反之亦然；④若某一语言能用有限自动机来识别，则它就能用有限状态文法生成，反之亦然。这一成果将形式语言引入数 学，使得形式语言真正诞生。1960年，算法语言ALGOL60报告发表。1961年，又发表了ALGOL60修改报告。在这两个报告中，第一次使用一种称为BNF 范式的形式方法来描述程序设计语言ALGOL60的语法。不久，人们即发现BNF 范式极其类似于形式语言理论中的上下文无关文法，从而打开了形式语言广泛应用于程序设计语言的局面，并给形式语言理论本身的研究以极大的推动，使它发展成为理论计算机科学的一个重要分支。 形式语言理论是从语言学衍生而来，作为一种理解自然语言的句法规律。在发展过程中人们发现其在计算机语言中的作用，计算机语言在计算机科学中，形式语言通常作为定义编程语言和语法的基础。对编程语言编译，使之转换成机器语言，形式语言在这一工作中有很重要的作用。形式语言推动了计算机学科的发展，并成为计算机学科里重要的分支。 19世纪中，布尔用数学方法研究思维规律的问题建立了逻辑代数，即布尔代数。肖斯塔科夫和仙农，独立地应用布尔代数于继电器接点电路的分析和综合,

军事理论第一章答案

第一章 1．举例说明“落后必然挨打”的历史教训。 答：英军以较少的兵力、较小的代价战胜了中国。究其原因，除了在客观上敌人兵器占有优势，战略战术运用得当，能集中大部兵力转沿海城市，占领经济命脉之地，战斗中常以正面攻击与侧翼包抄相结合之外，在主观上主要是清政府的腐败无能.近代中国一直在两种力量的左右下蹒跚前行，第一是有着五千年历史文化的传统惯性作用，第二是西方列强带来的工业化文明的威逼兼示范作用。自1840年以来，外敌不断入侵，国势日益衰微，列强割我土地、掠我资源、刮我财产、鱼肉我人民至中国土地上独“华人与狗不得入内”，其亡国灭种之恨，城下之盟之奇耻大辱，均使我国民刻骨铭心。“落后就要挨打”成了近代中国人心目中鲜血凝成的真理，也是历代仁人志士致力于发展现代化的强大的精神动力。 2．我国武装力量是由哪几部分组成的？分别说明。 答：（一）、中国人民解放军 中国人民解放军由现役部队和预备役部队组成 1、中国人民解放军现役部队由陆军、海军、空军和第二炮兵组成。它是中华人民共和国武装力量的主体。 （1）、陆军 陆军，是陆地上作战的军种。它担负在陆地歼灭敌人的任务，既能独立作战，又能与海军、空军联合作战。 中国人民解放军的陆军，现在已经发展成为诸兵种合成军种，具有较强的火力、突击力和机动力。在抵御外敌入侵，巩固国防，保卫祖国领土安全，抢险救灾，支援国家的社会主义经济建设等方面，做出了重要的贡献。 （2）、海军 海军，是以舰艇部队为主体，在海洋上作战的军种。现代海军通常由水面舰艇部队、潜艇部队、海军航空兵、海军岸防兵和海军陆战队等兵种及专业兵组成。主要装备作战舰艇、辅助舰船和飞机，配备有战略导弹、战术导弹、火炮、水中武器、战斗车辆等。具有在水面、水下、空中及对岸上实施攻防作战的能力；有的还具有实施战略袭击的能力。 （3）、空军 空军，是主要进行空中作战的军种。空军的基本任务是：担负国土防空，支援陆军、海军作战，对敌后实施空袭，进行空运和航空侦察。空军具有快速反应、高速机动、远程作战和猛烈突击的能力，既能协同其他军种作战，又能独立遂行战役、战略任务。空军是现代立体作战的重要力量，能对战争的进程和结局产生重大影响，在现代国防和现代战争中具有重要的地位和作用。 （4）、第二炮兵 中国人民解放军第二炮兵(简称二炮)，是以地战略导弹为主要装备、担负核反击战略作战任务的军种。地地战略导弹包括中程导弹(射程为1000—3000千米)、远程导弹(射程为3000—8000千米)和洲际导弹(射程为8000千米以上)。

形式语言与自动机理论蒋宗礼第三章参考答案

第三章作业答案 1．已知DFA M1与M2如图3－18所示。 (敖雪峰 02282068) (1) 请分别给出它们在处理字符串1011001的过程中经过的状态序列。 (2) 请给出它们的形式描述。 S q q 1 图3－18 两个不同的DFA 解答：(1)M1在处理1011001的过程中经过的状态序列为q 0q 3q 1q 3q 2q 3q 1q 3; M2在处理1011001的过程中经过的状态序列为q 0q 2q 3q 1q 3q 2q 3q 1; (2)考虑到用形式语言表示,用自然语言似乎不是那么容易,所以用图上作业法把它们用正则表达式来描述: M1: [01+(00+1)(11+0)][11+(10+0)(11+0)]* M2: (01+1+000){(01)*+[(001+11)(01+1+000)]*} ******************************************************************************* 2．构造下列语言的DFA ( 陶文婧 02282085 ) （1）{0，1}* ，1 （2）{0 ，1}+ ，1 （3）{x|x {0，1}+且x 中不含00的串} （设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）

（4）{ x|x∈{0，1}*且x中不含00的串} （可接受空字符串，所以初始状态也是接受状态） （5）{x|x∈{0，1}+且x中含形如10110的子串} （6）{x|x∈{0，1}+且x中不含形如10110的子串} （设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态） （7）{x|x∈{0，1}+且当把x看成二进制时，x模5和3同余，要求当x为0时，|x|=1,且x≠0时，x的首字符为1 } 1.以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入的符号为0，则进 入陷阱状态 2.设置7个状态：开始状态q s,q0:除以5余0的等价类，q1：除以5余1的等价类,q2:除以5 余2的等价类，q3:除以5余3的等价类，q4:除以5余4的等价类，接受状态q t

编译原理课后答案

第二章 2.3叙述由下列正规式描述的语言 (a) 0(0|1)*0 在字母表{0, 1}上,以0开头和结尾的长度至少是2的01 串 (b) ((ε|0)1*)* 在字母表{0, 1}上,所有的01串,包括空串 (c) (0|1)*0(0|1)(0|1) 在字母表{0, 1}上,倒数第三位是0的01串 (d) 0*10*10*10* 在字母表{0, 1}上,含有3个1的01串 (e) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)* 在字母表{0, 1}上,含有偶数个0和偶数个1的01串 2.4为下列语言写正规定义 C语言的注释，即以 /* 开始和以 */ 结束的任意字符串，但它的任何前缀（本身除外）不以 */ 结尾。 ［解答］ other → a | b | … other指除了*以外C语言中的其它字符 other1 → a | b | … other1指除了*和/以外C语言中的其它字符 comment → /* other* (* ** other1 other*)* ** */ (f) 由偶数个0和偶数个1构成的所有0和1的串。 ［解答］由题目分析可知，一个符号串由0和1组成，则0和1的个数只能有四种情况： x 偶数个0和偶数个1（用状态0表示）； x 偶数个0和奇数个1（用状态1表示）； x 奇数个0和偶数个1（用状态2表示）； x 奇数个0和奇数个1（用状态3表示）；所以， x 状态0（偶数个0和偶数个1）读入1，则0和1的数目变为：偶数个0和奇数个1（状态1） x 状态0（偶数个0和偶数个1）读入0，则0和1的数目变为：奇数个0和偶数个1（状态2） x 状态1（偶数个0和奇数个1）读入1，则0和1的数目变为：偶数个0和偶数个1（状态0） x 状态1（偶数个0和奇数个1）读入0，则0和1的数目变为：奇数个0和奇数个1（状态3） x 状态2（奇数个0和偶数个1）读入1，则0和1的数目变为：奇数个0和奇数个1（状态3） x 状态2（奇数个0和偶数个1）读入0，则0和1的数目变为：偶数个0和偶数个1（状态0） x 状态3（奇数个0和奇数个1）读入1，则0和1的数目变为：奇数个0和偶数个1（状态2） x 状态3（奇数个0和奇数个1）读入0，则0和1的数目变为：偶数个0和奇数个1（状态1） 因为，所求为由偶数个0和偶数个1构成的所有0和1的串，故状态0既为初始状态又为终结状态，其状态转换图： 由此可以写出其正规文法为： S0 → 1S1 | 0S2 | ε S1 → 1S0 | 0S3 | 1 S2 → 1S3 | 0S0 | 0 S3 → 1S2 | 0S1 在不考虑S0 →ε产生式的情况下，可以将文法变形为： S0 = 1S1 + 0S2 S1 = 1S0 + 0S3 + 1 S2 = 1S3 + 0S0 + 0 S3 = 1S2 + 0S1 所以： S0 = (00|11) S0 + (01|10) S3 + 11 + 00 (1) S3 = (00|11) S3 + (01|10) S0 + 01 + 10 (2) 解(2)式得： S3 = (00|11)* ((01|10) S0 + (01|10)) 代入(1)式得： S0 = (00|11) S0 + (01|10) (00|11)*((01|10) S0 + (01|10)) + (00|11) => S0 = ((00|11) + (01|10) (00| 11)*(01|10))S0 + (01|10) (00|11)*(01|10) + (00|11) => S0 = ((00|11)|(01|10) (00|11)*(01|10))*((00|1

浙江大学军事理论各章节答案(1~11章)

各章节答案 中国国防与历代军事思想 34 我国贯彻积极防御的军事战略方针。T 46 中国的古代军事思想成熟于下列的哪个时期？(D) A. 唐朝 B. 汉朝 C. 西周 D. 春秋战国 49 世界最早的管形火器长竹杆火器和突火枪发明于下面哪个朝代？(B) A. 北宋 B. 南宋 C. 元朝 D. 明朝 52 《孙子兵法》提出"不战而屈人之兵"的战略思想，并提出"兵者，以?为植，以文为种； 武为表，文为里"的治国思想。（ F ） 54 提出“天下虽安，忘战必危”的战备观的，是：C A. 孙子 B. 吴子 C. 田穰苴 D. 尉缭子 81 毛泽东军事思想的核心是：B A. 军事辩证法 B. 人民战争思想 C. 人民军队思想 D. 人民战争的战略战术 85 我军的基本作战方针是：(C) A. 击溃战 B. 消耗战 C. 歼灭战 D. 阵地战 歼灭战就是歼灭敌人一切有生力量。（ F ）[保存自己，消灭敌人] 87 毛泽东认为，发生战争的根本原因是：(D) A. 霸权主义 B. 帝国主义 C. 政治冲突 D. 私有制与阶级的出现 87 战争的性质和结局受什么决定？A (最后一行） A. 政治 B. 军事 C. 经济 D. 国防实力 93 研究和指导战争必须着眼于战争的什么差异？BCD A. 规模 B. 地域 C. 性质 D. 时间 95 100 正义战争是人民战争，人民战争也一定是正义战争。错 (人民战争必然是正义战争，正义战争不一定是人民战争） -------世界军事领域正在发生的军事技术革命的核心是：(A) A.信息技术 B. 综合集成技术 C. 多军兵种合成 D. 新作战思想 --------国家利益包括：（ABCD ） A 领土主权完整B政治制度C文化传统D国民经济 人的主观能动性是战争胜负的决定因素之一。T 西周时期的军事思想奠定了中国古代军事思想的根基。T 第六章精确制导技术 159 惯性制导系统是不断修正导弹的加速度，从而攻击目标。F 测量加速度，修正轨道161自主式/惯性制导的导弹一经发射，就与发射点及目标点无关，而只与导弹本身有关。T 对于地形匹配制导，导弹飞经地域之地形越复杂，制导精度就越高。（T ） 对于地形匹配制导的导弹，地形越复杂，则制导精度越高。T 地形匹配制导的精度与射程有关而与地形无关.F 162 精确制导武器利用ＧＰＳ系统可以大大提高制导精度。T GPS制导有以下特点：ABC A. 命中精度高 B. 制导距离远 C. 发射后不管 D. 抗干扰能力强

形式语言与自动机课后习题答案

形式语言与自动机课后作业答案 第二章 4．找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。 答：G={N,T,P,S} 其中N={S,A,B,C,D} T={x,y} 其中x∈{所有字母} y∈{所有的字符} P如下: S→x S→xA A→y A→yB B→y B→yC C→y C→yD D→y 6．构造上下文无关文法能够产生 L={ω/ω∈{a,b}*且ω中a的个数是b的两倍} 答：G={N,T,P,S} 其中N={S} T={a,b} P如下: S→aab S→aba S→baa S→aabS S→aaSb S→aSab S→Saab S→abaS S→abSa S→aSba S→Saba S→baaS S→baSa S→bSaa S→Sbaa 7．找出由下列各组生成式产生的语言（起始符为S） (1)S→SaS S→b (2)S→aSb S→c (3)S→a S→aE E→aS 答：（1）b(ab)n /n≥0}或者L={(ba)n b/n≥0} (2) L={a n cb n /n≥0} (3)L={a2n+1 /n≥0} 第三章 1．下列集合是否为正则集，若是正则集写出其正则式。 （1）含有偶数个a和奇数个b的{a,b}*上的字符串集合 （2）含有相同个数a和b的字符串集合 （3）不含子串aba的{a,b}*上的字符串集合 答：（1）是正则集，自动机如下 (2) 不是正则集，用泵浦引理可以证明，具体见17题（2）。

(3) 是正则集 先看L’为包含子串aba的{a,b}*上的字符串集合 显然这是正则集，可以写出表达式和画出自动机。（略） 则不包含子串aba的{a,b}*上的字符串集合L是L’的非。 根据正则集的性质，L也是正则集。 4．对下列文法的生成式，找出其正则式 （1）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→abS A→bB B→b B→cC C→D D→bB D→d （2）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→cC A→bB B→bB B→a C→D C→abB D→d 答：(1) 由生成式得： S=aA+B ① A=abS+bB ② B=b+cC ③ C=D ④ D=d+bB ⑤ ③④⑤式化简消去CD，得到B=b+c(d+bB) 即B=cbB+cd+b =>B=(cb)*(cd+b) ⑥ 将②⑥代入① S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =>S=(aab)*(ab+ε)(cb)*(cd+b) (2) 由生成式得： S=aA+B ① A=bB+cC ② B=a+bB ③ C=D+abB ④ D=dB ⑤ 由③得 B=b*a ⑥ 将⑤⑥代入④ C=d+abb*a=d+ab+a ⑦ 将⑥⑦代入② A=b+a+c(d+b+a) ⑧ 将⑥⑧代入① S=a(b+a+c(d+ab+a))+b*a =ab+a+acd+acab+a+b*a 5.为下列正则集，构造右线性文法： (1){a,b}* (2)以abb结尾的由a和b组成的所有字符串的集合

编译原理课后习题答案

第1 章 1、编译过程包括哪几个主要阶段及每个 阶段的功能。 答案：编译过程包括词法分析、语法分析、语义分析和中间代码生成、优化、目标代码生成5 个阶段。词法分析的功能是对输入的高级语言源程序进行词法分析，识别其中的单词符号，确定它们的种类，交给语法分析器，即把字符串形式的源程序分解为单词符号串形式。语法分析的功能是在词法分析结果的基础上，运用语言的语法规则，对程序进行语法分析，识别构成程序的各类语法范畴及它们之间的层次关系，并把这种层次关系表达成语法树的形式。词义分析和中间代码生成的功能是在语法分析的基础上，对程序进行语义分析，“理解”其含义，产生出表达程序语义的内部表达形式（中间代码）。优化的功能是按照等价变换的原则，对语义分析器产生的中间代码序列进行等价变换，删除其中多余的操作，对耗时耗空间的代码进行优化，以期最后得到高效的可执行代码。目标代码生成的功能是把优化后的中间代码变换成机器指令代码，得到可在目标机器上执行的机器语言程序。 第2 章 1、写一上下文无关文法G，它能产生配 对的圆括号串（如：(),(()),()(())等，甚至 包括0 对括号） 文法为：S→(L)|LS|L L→S| ε 2 、已知文法G ：E→E+T|E-T|T T→T*F|T/F|F F→(E) |i （1）给出i+i*i,i*(i-i)的最左推导，最右推导以及语法树。 （2）i-i+i 哪个算符优先。 【解答】 （1）最左推导：E?E+T?T+T? F+T ? i+T ? i+T*F ? i+F*F ?i+i*F ?i+i*i E?T?T*F? F*F ? i*F ? i*(E) ? i*(E-T) ? i*(T-T) ? i*(F-T) ? i*(i-T) ? i*(i-F) ?i*(i-i) 最右推导：E?E+T?E+T*F? E+T*i ? E+F*i ? E+i*i ? T+i*i ? F+i*i ? i+i*i E?T?T*F? T*(E) ? T*(E-T) ? T*(E-F) ? T*(E-i) ? T*(T-i) ? T*(F-i) ?T*(i-i) ? F*(i-i) ?i*(i-i) i+i*i 以及i*(i-i)的语法树如下所示： （2）i-i+i 的语法树如下图所示。 从上图的语法树可知：“-”的位置位 于“+”的下层，也就是前面两个i 先进 行“-”运算，再与后面的i 进行“+” 运算，所以“-”的优先级高于“+”的 优先级。 3 、文法G: E→ET+|T T→TF*|F F→FP↑|P P→E|i （1）试证明符号串TET+*i↑是G 的一 个句型(要求画出语法树). （2）写出该句型的所有短语,直接短语和句柄. 【解答】（1）采用最右推导： E?T?F? FP↑? Fi↑? Pi↑? Ei↑ ? Ti↑? TF*i↑? TP*i↑? TE*i↑? TET+*i↑ 语法树如下图所示。 从文法G 的起始符号出发，能够推导 出符号串TET+*i↑，所以给定符号串是文法G的句型。 (2) 该句型的短语有： ET+,TET+*,i ,TET+*i↑ 直接短语有：ET+, i 句柄是：ET+ 4、已知文法G：S→iSeS|iS|i ，该文法 是二义文法吗？为什么？ 【解答】该文法是二义文法。 因为对于句子iiiei 存在两种不同的最 左推导： 第 1 种推导：S? iSeS? iiSeS? iiieS? iiiei 第2种推导：S?iS?iiSeS?iiieS?iiiei 第3 章 1、用正规式描述下列正规集： （1）C 语言的十六进制整数； （2）以ex 开始或以ex 结束的所有小写字母构成的符号串； （3）十进制的偶数。 【解答】 （1）C 语言十六进制整数以0x 或者0X 开头，所以一般形式应该为（+|-|ε） (0x|0X)AA*，其中前面括号表示符号， 可以有正号、负号，也可以省略（用ε表示）默认是正数，A 表示有资格出现在十六进制整数数位上的数字，AA*表示一位或者多位（一个或者多个数字的

军事理论第二章答案

第二章 1．中国古代军事思想对军事思想的发展作出了哪些巨大的贡献？ 答：大国防安国主义的道德内涵，即是大国防爱国主义，它所蕴含的现代价值意义就是：一个真正的爱国主义者，应责无旁贷地承担起“安国”的历史责任和使命，为提高综合国力作出自己应有的贡献；一个欲立于不败之地的国家和民族，就应重视物质文明建设和精神文明建设，使之都处于时代的领先地位。 当今世界，是一个充满矛盾和激烈竞争的世界。但是，由于全球经济的一体化和多极化发展趋势，使一个国家的综合国力的发展被限定在一体化的范围内，而且越来越受到一体化的制约。在这方面，发达国家理应为世界经济的繁荣作出更多的贡献和牺牲，否则它的发展就要受到限制。总之，当代的一个国家综合国力的增强，是在激烈的世界竞争和全球经济一体化的环境中实现的，只有顺应“要和平、求合作、促发展”的时代潮流，才能更有利于综合国力的增强，从而达到“安国”之目的。 中华武德文化史上有两句古语，一是“忘战必危”，二是“好战必亡”。尤其是在环球相对“变小”、战争的破坏力愈来愈大的当今世界，“安国”与安国际社会融为一体，安己之国与安人之国相辅相成，国际社会的安全度以每个国家的安全系数为条件。因此，孙子“军争为危”命题的真理性，越来越具有普遍的、现实的意义，应引起国际社会和各国人民的高度重视。 2．毛泽东军事思想科学体系的基本内容有哪些？ 答:人民战争思想,人民军队建设思想,人民战争的战略战术思想，国防建设思想，战争观和军事问题方法论。 3．人民战争的战略战术内容有哪些？ 答：主要内容有：保卫自己，消灭敌人的战争目的；积极防御的战略指导思想；运动战、阵地战、游击战等作战形式；集中优势兵力，各个歼灭敌人的作战法则；审时度势、灵活机动的指挥艺术。 4．如何认识高技术条件下的人民战争？ 答：第一，人是武器的主人；人不仅研制武器，而且使用武器，只有掌握高科技知识的人，才能掌握和使用高技术武器；第二，打赢高技术战争离不开与之相适应的作战理论；第三，高技术战争不仅是钢铁战，电子战，更是“智力战”。 5．资产阶级军事思想是怎样逐步发展的？ 答：文艺复兴时期，欧洲新兴资产阶级为反对教会和封建制度的统治，建立统一的中央集权的民族国家，即开始注意到军事的重要性。15世纪，意大利的政治思想家N.马基雅维利在总结古罗马历史经验基础上提出，君主要巩固自己的权势,必须专心致力于战争,切实掌握军事力量。这是资产阶级军事思想的最早发端。 16、17世纪，尼德兰和英国相继发生资产阶级革命。资本主义制度开始在西方一个又一个国家确立。经济的迅速发展，科学技术的进步，推动着社会思想包括军事思想的不断变革。频繁的战争实践，又为从事军事理论著述提供了必要条件。到18世纪，出现了资产阶级军事思想的第一批著作家，其中较著名的有英国的劳埃德，法国的J.A.de吉贝尔，普鲁士的比洛，奥地利的卡尔大公，俄国的苏沃洛夫等人。

形式语言与自动机理论试题答案解析

形式语言与自动机理论试题答案解析 一、按要求完成下列填空 1. 给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集 （2x4'） (1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}} (2) {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}} 2. 设∑={0,1},请给出∑上的下列语言的文法 （2x5'） (1)所有包含子串01011的串 S →X01011Y X →ε|0X|1X Y →ε|0Y|1Y (2)所有既没有一对连续的0，也没有一对连续的1的串 A →ε |A ’|A ” A’ →0|01|01A ’ A ” →1|10|10A ” 3. 构造识别下列语言的DFA 2x6' (1) {x|x ∈{0，1}+且x 以0开头以1结尾} （设置陷阱状态，当第一个字符为1时，进入陷阱状态） 1 S 1 1 0,10 (2) {x|x ∈{0，1} + 且x 的第十个字符为1} （设置一个陷阱状态，一旦发现x 的第十个字符为0，进入陷阱状态） 1S 0,1 0,10,10,10,110,0,10,10,10,1 0,1

二、判断（正确的写T ，错误的写F ） 5x2' 1.设1R 和2R 是集合{a,b,c,d,e}上的二元关系，则 3231321)(R R R R R R R ? ( T ) 任取(x.,y),其中x,y },,,,{e d c b a ∈，使得321)(),(R R R y x ∈。 )),(),((321R y z R R z x z ∈∧∈?? },,,,{e d c b a z ∈ )),(),(),((321R y z R z x R z x z ∈∧∈∧∈?? )),(),(()),(),((3231R y z R z x z R y z R z x z ∈∧∈?∧∈∧∈?? 3231),(),(R R y x R R y x ∈∧∈? 3231),(R R R R y x ∈? 2.对于任一非空集合A ，Φ?A 2 ( T ) 3.文法G ：S A|AS A a|b|c|d|e|f|g 是RG ( F ) 4.3型语言 2型语言 1型语言 0型语言 ( F ) 5.s （rs+s ）*r=rr *s （rr *s ）* ( F ) 不成立，假设r,s 分别是表示语言R ，S 的正则表达式，例如当R={0}，S={1}, L(s(rs+s)*r)是以1开头的字符串，而L(rr*s(rr*s)*)是以0开头的字符串.L(s(rs+s)*r) ≠ L(rr*s(rr*s)*) 所以s(rs+s)*r ≠ rr*s(rr*s)*,结论不成立 三、设文法G 的产生式集如下，试给出句子aaabbbccc 的至少两个不同的推导（12分）。 aSBC aBC S |→ ab aB → bB →bb CB →BC bC →bc cC →cc

形式语言与自动机的关系

形式语言与自动机的关系研究 新疆师范大学数理信息学院数学03-6班摘要： 形式语言的直观意义，自动机的直观意义，形式语言的定义， 形式语言的特征，语法的分类，自动机的定义，自动机的分 类，各种自动机的定义，形式语言和自动的的关系，自动机 的对语言的例子 基本关键词： 形式语言的定义；自动机的定义；形式语言和自动机的关系 1，形式语言的直观意义 α→的直观地讲，形式语言是用来精确描述语言和它结构的手段。它一重写规则β α,均为字符串。重写规则就是在包含α的字符穿中遇见规则左边的形式来表示，其中，β α时，α部分重新写为右边的β。这样一个初设的字符串通过不断地运用重写规则，就可以到另一个字符串。通过选择不同的规则并且以各种不同的顺序来运用最这些规则，如果指 定一个初始符，某规则以其为左部，一组规则就可以构成一个语法。 2，形式语言的定义

形式语法是一个四元组G=（N, V , P, S ）,其中N 是非终结符的有限集合，有时也称变量，它们相当于各种句法范畴。V 是终结符的有限集合，若语法生成的是自然语言，这些终端语符就相当于这种语言中具体的词，终端 语符集 这种语言的词库，P 是以重写规则的有限集合，基本形式P }{βα→，即""βα改写为，其中箭头表示指令，一条规则就是一个机械性的操作程序，用来演算它联系着的两侧语符集或语符序列之间的关系，而S 是一个特定的初始符； 3，语法的分类 乔姆斯在他的著名【文章】中根据重写规则将语法分成四类：正则语法，上下文有关语法，上下文无关语法；有这些语法生成的语言是正则语言，，上下文有关语言，上下文无关语言，递归数集合。 a 如果P 中的规则，满足如下的形式：x A Bx A →→或，，其中，A,B 是非终结符，x 是终结符，则G 称为正则语法（简称为FSG ）。 b 如果P 中的规则，满足如下的形式：α→A ,其中，A 是非终结符, α是由N 和V 中字符所组成的字符串（或可表示为()*∈V N α,*意味着它右边的字符可以重复0到任何 多次），则G 称为上下文无关语法（简称为CFG ）。 d 如果P 中的规则，满足如下的形式：αγββα→A ,其中，A 是非终结符,γβα,,,是字符串，且γ至少包含一个字符，则G 称为上下有无关语法（简称为CSG ）。 d 如果P 中的规则，满足如下的形式：其中，α，β是字符串，则G 称为无限制重写系统。 对于以上任何一种语法，两个字符串之间一次派生关系?可定义为： 如果y x →是P 中的规则，βαβαy x ?。 字符串α，β有多次派生关系* ?则是说，通过多次应用一次派生关系，从α可派生出β，并记为α* ?β： n αβαα==,0，而对n i i n i +?-=αα,1,....0。 给定以语法，其语言定义为所有合法终结字符串的集合。合法终结字符串是指由初始符S 出发，运用重写规则而派生得终结字符串，即， (){}ααα**;?∈=S V G L 例子：假设G=(N, V , P, S), N={S, A} , V={0, 1}, P={0,0,1→→→A A A A S } 则 ，{}110)(≥=m G L m 是正则语法，在V={0, 1}上它所对应的正则表达式是100*。 形式语言的特征： ⑴ 高度抽象化（采用形式化的手段，专用符号，数学公式来描述语言的，结构关系，这种关系是抽象的）。

编译原理(清华大学 第2版)课后习题答案

第三章 N=>D=> {0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD L={a |a(0|1|3..|9)n且 n>=1} (0|1|3..|9)n且 n>=1 {ab,} a n b n n>=1 第6题. (1) <表达式> => <项> => <因子> => i (2) <表达式> => <项> => <因子> => (<表达式>) => (<项>) => (<因子>)=>(i) (3) <表达式> => <项> => <项>*<因子> => <因子>*<因子> =i*i (4) <表达式> => <表达式> + <项> => <项>+<项> => <项>*<因子>+<项> => <因子>*<因子>+<项> => <因子>*<因子>+<因子> = i*i+i (5) <表达式> => <表达式>+<项>=><项>+<项> => <因子>+<项>=i+<项> => i+<因子> => i+(<表达式>) => i+(<表达式>+<项>) => i+(<因子>+<因子>) => i+(i+i) (6) <表达式> => <表达式>+<项> => <项>+<项> => <因子>+<项> => i+<项> => i+<项>*<因子> => i+<因子>*<因子> = i+i*i 第7题

第9题 语法树 s s s* s s+a a a 推导: S=>SS*=>SS+S*=>aa+a* 11. 推导:E=>E+T=>E+T*F 语法树: E +T * 短语: T*F E+T*F 直接短语: T*F 句柄: T*F 12．

短语： 直接短语： 句柄： 13.(1)最左推导：S => ABS => aBS =>aSBBS => aBBS => abBS => abbS => abbAa => abbaa 最右推导：S => ABS => ABAa => ABaa => ASBBaa => ASBbaa => ASbbaa => Abbaa => a1b1b2a2a3 (2) 文法：S → ABS S → Aa S →ε A → a B → b (3) 短语：a1 , b1 , b2, a2 , , bb , aa , abbaa, 直接短语： a1 , b1 , b2, a2 , , 句柄：a1 14 (1) S → AB A → aAb | ε B → aBb | ε (2) S → 1S0 S → A A → 0A1 |ε 第四章 1. 1. 构造下列正规式相应的DFA (1)1(0|1)*101 NFA (2) 1(1010*|1(010)*1)*0 NFA