编译原理第三章答案
- 格式：docx
- 大小：1.71 MB
- 文档页数：9
“编译技术”第三章作业
3-1构造下列正规式相应的DFA：
（1） 1(0|1)*101
（2） a((a|b)*|ab*a)*b
解：
由转换系统构造确定有穷自动机
状态集I I0 I1
S Φ ACB
ACB CB CBi
CB CB CBi CBi CBj CBi
CBj CB CBiZ
CBiZ CBj CBi
对状态重命名：
状态集I I0 I1
T0 Φ T1
T1 T2 T3 T2 T2 T3
T3 T4 T3
T4 T2 T5
T5 T4 T3
DFA的状态转换图：
（2）
构造该正规式的装换系统：
由转换系统构造确定有穷自动机
状态集I Ia Ib
S ABCDEF Φ
ABCDEF BCDEFG BCDEFZ
BCDEFG BCDEFG BCDEFZ
BCDEFZ BCDEFG BCDEFZ
对状态重命名：
状态集I I0 I1
T0 T1 Φ
T1 T2 T3
T2 T2 T3
T3 T2 T3
DFA的状态转换图：
3-2 对下面的FA，将它确定化并最小化。
S0S3S1εbbS2cεεa
解：
由转换系统构造确定有穷自动机
状态集I Ia Ib Ic
S0 S1 S2 S3 S0 S1 S2 S3 S1 S3 S2 S3
S1 S3 Φ S1 S3 Φ
S2 S3 Φ Φ S2 S3
对状态重命名：
状态集I Ia Ib Ic
T0 T0 T1 T2
T1 Φ T1 Φ
T2 Φ Φ T2
DFA的状态转换图：
最小化：
初始划分={T0,T1,T2}
{T0,T1,T2}a={T0, Φ, Φ}，所以划分为（{ T0},{Φ, Φ}）即{T0}
3-3 给出下述文法所对应的正规式：
S0A|1B
A1S|1
B0S|0
解：
S→0A→01
S→0A→01S→010A→0101S→0101OA→0101O1S…
S→1B→10
S→1B→10S→101B→1010S→10101B→101010S…
所以可得正规式=（01|10）（01|10）* 3-4 构造下述文法G[S]的自动机：
SA0
SA0|S1|0
该自动机是确定的吗？若不确定，则对它确定化。该自动机可识别的语言是什么？
解：
文法转换为自动机：
因为是左线性文法，要增加一个开始状态X，并将开始符号S看成终态。
因为A经0可达到不同的状态，所以，该自动机为NFA。
确定化：
状态集I I0 I1
X A Φ
A AS Φ
AS AS A
对状态重命名：
状态集I
I0 I1
X A Φ
A B Φ
B B A
该自动机表达的语言用正规式表示为：00（0|10）*
3-5 试用有限自动机理论证明下列正规表达式是等价的。
（1） (a|ba)*b
（2）(a*ba)*a*b
解：
（1）
（2）
因为最小化后，两者的状态图是一样的，都为：
所以正规式(a|ba)*b和正规式(a*ba)*a*b是等价的。
