第三章
4.指出哪些串是自动机可接受的 xy xyxxy yyyx xyyxyxyxxy
第三章
5.将下图所示的 非确定有限自动 机 (NFA) 变 换 成 等价的确定有限 自动机(DFA)。
b
a
2
1 a
X
a
b
b b
3
4
a
a
Y b
b
a
2
第三章
1 a
b
X b
a b
解:用子集法将NFA确定化，如
3
a
0
b
1
a
➢ 最小化：此状态图已经为最简了。
第三章
1.指出与正规式匹配的串。 a) (ab|b)*c 与后面的那些串匹配？
ababbc abab c aaabc babc b) ab*c*(a|b)c 与后面的那些串匹配？
acac acbbc abc abbcac acc c) (a|b)aa*(ba)* 与后面的那些串匹配?
解：先由产生式得: B=aA 将B代入A中得:A=bA|aaA|b =(b|aa)A|b 利用规则（A->xA|y）得: A= (b|aa) * b 将A代入S中得:S=a (b|aa) * b 即为所求正规式
3.4 给出文法G[S]，构造相应最小的DFA。 G：S→aS | bA | b A→aS
解：由文法到NFA的转换有两种方法： ① 由文法到正规式，再由正规式到NFA
先由产生式得: A = aS 将A代入S中得: S = aS|bA|b = aS|baS|b
= (a|ba)S|b 利用规则（A->xA|y）得: S= (a|ba)*b
文法G对应的正规式为(a|ba)*b ，其对应的NFA的
{0,1,2,5}, {4}, {3,6,7}
➢ 对于非终态集，在输入字符a、
b后按其下一状态落入的状态集 不同而最终划分为
{0}, {1}, {2}, {5}, {4}, {3,6,7}
ab 012 134 2 －5
ba ababa aa baa bba
第三章
2. 为下边所描述的串写正规式，字母表是 {0, 1}.
a) 以01 结尾的所有串
(0|1)*01
b) 只包含一个0的所有串
1*01*
c) 包含偶数个1但不含0的所有串 (11)*
d) 包含偶数个1且含任意数目0的所有串
(0*10*10*)*
e) 包含01子串的所有串
{3,4,Y} {2,3,4,Y} {3,4,Y}
7
a
Y
b
a
b
1
2
3
4
－
5
3
6
3
5
5
7
6
6
6
7
第三章
➢ 上图所对应的DFA如下所示。
a
3 a
b
a
0
a1ba
0
4
1
6
b
2
3
b
2
b
a
4
b
5
7
5
b
6
a b
7
ab 12 34 －5 36 35 57 66 67
第三章
➢ 对上图的DFA进行最小化。首先将
状态分为非终态集和终态集两部分： 0
{0,1,2,5}和{3,4,6,7}。
1
➢ 由终态集可知，对于状态3、6、7， 2
无论输入字符是a还是b的下一状态 3
均为终态集，而状态4在输入字符b
4 5
的下一状态落入非终态集，故将其 6
化为分{0,1,2,5}, {4}, {3,6,7}
7
ab 12 34 －5 36 35 57 66 67
第三章
第二章
2.5 证明下面的文法是二义性的。
S→iSeS | iS | i 答：对句子iiiei对应两棵不同的语法树
S
S
iS
i Se S
i Se S
i Si
i
i
i
第二章
2.9 设有文法G[T]: T→T*F|F F→ FîP|P P→(T)|i
分析句型T*P î(T*F)的短语、直接短语和句柄
答：句型T*P î(T*F)的语法树：
T
五棵子树对应五个短语T*P î(T*F), P î(T*F), T * F
P, (T*F), T*F
➢两层子树(简单子树)的末端结点构成直接短语 F î P
两棵两层子树对应两个直接短语：
P , T*F
P (T)
➢位于最左边的两层子树的末端结点构成句柄： P
T *F
第三章
3.1 构造正规式1(0|1)*101相应的NFA
第三章
正规式：(a|ba)*b
产生式 S→aS S→bA S→b A→aS
转换函数 f(S,a)=S f(S,b)=A f(S,b)=T f(A,a)=SaSbA Nhomakorabeaa
b
T
第三章
➢ 将NFA确定化为DFA
a
S
b
A
a
b
T
I
Ia
{S} 0 {S}
{A,T} 1 {S}
Ib 0 {A,T} 1 0 --
➢ 如右图所示
(0|1)*01(0|1)*
f) 不包含01子串的所有串
1*0*
第三章
3. 请描述下面正规式定义的串. 字母表S = {x, y}。
a) x(x|y)*x 必须以 x 开头和x结尾的串
b) x*(yx+)*x* 每个 y 至少有一个 x 跟在后边的串
c) (x|y)*(xx|yy) (x|y)* 所有含两个相继的x或两个相继的y的串
1
(0|1)* 1
0
1
X
A
B
C
D
Y
0|1
1
ε
ε
1
0
1
X
A
E
B
C
D
Y
0,1
1
ε
ε
1
0
1
X
A
E
B
C
D
Y
第三章
3.1 构造正规式1(0|1)*101相应的NFA
(0|1)*
1
1
0
1
X
A
B
C
Y
0,1
1
1
0
1
X
A
B
C
Y
0,1
1
ε
ε
1
0
1
X
A
E
B
C
D
Y
第三章
3.5 给出下述文法所对应的正规式。 G：S→aA A→bA | aB | b B →aA
4
下图所示。
a
I
Ia
Ib
{X}
{1}
{3}
0
{1} {3}
{2,3,Y} －
{3,Y} {3,4}
1 重新命名
2
{2,3,Y} {2,3,Y} {2,3,4,Y}
3
{3,Y}
{2,3,Y} {3,4}
4
{3,4}
{3,4}
{3,4,Y}
5
{2,3,4,Y} {2,3,4,Y} {2,3,4,Y}
6
第二章
2.2 设有文法G[N]:
N->D | ND
D->0|1|…|9
(1) G[N]定义的语言是什么？
(2) 请给出句子0123的最左推导和最右推导。
N ND NDD NDDD DDDD 0DDD 01DD 012D 0123 N ND N3 ND3 N23 ND23 N123 D123 0123
状态转换图为：
第三章
3.4 给出文法G[S]，构造相 应最小的DFA。
G：S→aS | bA | b A→aS 解：② 由文法直接到NFA 文法对应的有自动
M=({S,A, T}, {a,b}, f, S, {T}) 其对应的状态转换图为：
产生式 S→aS S→bA S→b A→aS
转换函数 f(S,a)=S f(S,b)=A f(S,b)=T f(A,a)=S