《编译原理》课后习题答案第四章
解方程组 S 的解： S=0A|1B A=1S|1 B=0S|0
将 A、B 产生式的右部代入 S 中
S=01S|01|10S|10=（01|10）S|（01|10）所以：S= (01|10)*(01|10) 第 9 题
将下图的 DFA 最小化，并用正规式描述它所识别的语言。
c b a b 1 3 6 d c 5 b b d a 2 a 4 b 7 b
答案：
令P0＝（｛1,2,3,4,5｝,｛6,7｝）用b进行分割：
P1＝（｛1,2｝,｛3,4｝,｛5｝,｛6,7｝）再用a、b、c、d进行分割，仍不变。 再令｛1,2｝为 A，｛3，4｝为 B，｛5｝为 C，｛6，7｝为 D。
最小化为：
c b a A B a d b C D
b
盛威网（www.snwei.com）专业的计算机学习网站
17
《编译原理》课后习题答案第四章 *
a(c|da)*
b+
盛威网（www.snwei.com）专业的计算机学习网站18
r=ba(c|da)bb=b*
*
*
《编译原理》课后习题答案第四章
附加题
问题 1：
为下边所描述的串写正规式，字母表是 {a,b}. a) 以 ab 结尾的所有串
b) 包含偶数个 b 但不含 a 的所有串 c) 包含偶数个 b 且含任意数目 a 的所有串 d) 只包含一个 a 的所有串 e) 包含 ab 子串的所有串 f) 不包含 ab 子串的所有串 答案：
注意 正规式不唯一 a) (a|b)*ab b) (bb)*
c) (a*ba*ba*)* d) b*ab*
e) (a|b)*ab(a|b)* f) b*a* 问题2：
请描述下面正规式定义的串. 字母表 {0，1}. a) 0*(10+)*0* b) (0|1)*(00|11) (0|1)* c) 1(0|1)*0 答案：
a) 每个 1 至少有一个 0 跟在后边的串 b) 所有含两个相继的0或两个相继的1的串 c) 必须以 1 开头和0结尾的串 问题3：
构造有穷自动机.
a) 构造一个 DFA，接受字母表 {0, 1}上的以 01 结尾的所有串 b) 构造一个DFA，接受字母表 {0, 1}上的不包含01 子串的所有串. c) 构造一个NFA，接受字母表
{x,y}上的正规式x(x|y)*x描述的集合
盛威网（www.snwei.com）专业的计算机学习网站
19
《编译原理》课后习题答案第四章
d) 构造一个NFA，接受字母表 等价的DFA.以及最小状态DFA 答案：
{a, b}上的正规式(ab|a)*b+描述的集合并将其转换为
b)
c)
盛威网（www.snwei.com）专业的计算机学习网站
20
《编译原理》课后习题答案第四章
最小化的 DFA
问题 4：
设有如图所示状态转换图，求其对应的正规表达式。
可通过消结法得出正规式 R=(01)*((00|1)(0|1)*|0) 也可通过转换为正则文法，解方程得到正规式。 问题 5：
盛威网（www.snwei.com）专业的计算机学习网站
21
相关推荐：
loading