网站地图
【www.arisingsemi.com--语言培训】
奇数表 3.2 是非判断，对下面的陈述，正确的在陈述后的括号内写T，否则写F。(1)有穷自动机接受的语言是正则语言。（）
(2)若r1和r2是Σ上的正规式，则r1|r2也是。
（）
(3)设M是一个NFA，并且L(M)＝{x,y,z}，则M的状态数至少为4个。（）
(4)令Σ＝{a,b}，则Σ上所有以b为首的字构成的正规集的正规式为b*(a|b)*。
（）
(5)对任何一个NFA M，都存在一个DFA M"，使得L(M")=L(M)。（）
(6)对一个右线性文法G，必存在一个左线性文法G"，使得L(G)=L(G")，反之亦然。（）
答案(1) T (2) T (3) F(4) F (5) T (6) T
3.3 描述下列各正规表达式所表示的语言。
(1) 0(0|1)*0
(2) ((ε|0)1*)*
(3) (0|1)*0(0|1)(0|1)
(4) 0*10*10*10*
(5) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)*
3.4 对于下列语言分别写出它们的正规表达式。
(1) 英文字母组成的所有符号串，要求符号串中顺序包含五个元音。
(2) 英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。
(3) Σ={0,1}上的含偶数个1的所有串。
(4) Σ={0,1}上的含奇数个1的所有串。
(5) 具有偶数个0和奇数个1的有0和1组成的符号串的全体。
(6) 不包含子串011的由0和1组成的符号串的全体。
(7) 由0和1组成的符号串,把它看成二进制数，能被3整除的符号串的全体。
3.6 给出接受下列在字母表{0,1}上的语言的DFA。
(1) 所有以00结束的符号串的集合。
(2) 所有具有3个0的符号串的集合。
3.7构造等价于下列正规表达式的有限自动机。
(1)10|（0|11）0*1
(2)((0|1)*|(11))*
(2) δ（q0，0）=q1 δ（q0，1）=q2
(3) δ（q1，0）=q1 δ（q1，1）=q3
(4) δ（q2，0）=q3 δ（q2，1）=q1
(5)
(6) (2) DFA M=({0，1}，{q0}，q0，{q0}，δ)
(7) 其中δ定义如下:
(8) δ（q0，0）=q0 δ（q0，1）=q0
(9)
3.8 给定右线性文法G：
S->0S|1S|1A|0B
A->1C|1
B->0C|0
C->0C|1C|0|1
试求一个于G等价的左线性文法G"
3.9 试对于下列正规表达式使用证明定理3。5的构造算法构造非确定的有限自动机。请给出每个自动机在处理输入符号串ababbab的过程中的动作序列。
(1) (a|b)*
(2) (a*|b*)*
(3) ((ε|a)b*)*
3.10 转换练习3.9中的每个 NFA 为 DFA 。
并给出每个DFA在处理输入符号串ababbab的过程中的动作序列。
3.11 试把练习3.10中得到的DFA的状态给以最小化。
3.12 我们可以证明两个正规表达式是等价的，如果它们的最小状态DFA是相同的（除了状态的名字以外）。利用这一结论，请说明下列正规表达式都是等价的。
(1) (a|b)*
(2) (a*|b*)*
(3) ((ε|a)b*)*
3.13 对于下列正规表达式构造最小状态的DFA。
(1) (a|b)*a(a|b)
(2) (a)b)*a(a|b)(a|b)
5． 对如下文法：
G[S] ： S a b S | a a B | a d
B b b B | b
分别给出句子abaabbb和ad的句柄
句子ad的语法分析树为：
句子abaabbb的语法分析树为:
所以句子abaabbb的句柄是b；句子ad的句柄是ad .
二、（10分）说明如下文法是否是LL
（1）文法，若不是，将其转换为LL
（1）文法。
最后给出该文法的LL
（1）分析表。
G[A]： A B e
B B b | a
文法中有左递归，不是LL(1)文法。
转换为 G′ ： A B e
B a B′
B′ b B′ | λ
Predict(A B e) ={ a }
Predict(B a B′) ={ a }
Predict(B′ b B′) ={ b }
Predict(B′ λ ) ={ e }
LL(1)分析表:
a
b
e
A
B e
B
a B′
B′
b B′
λ
4. 给出识别正则表达式(（a|bc）*d)+的NFA 。
5． 已知文法G[S]： S → S；G│G
G → G(T)│ H
H → a │ (S)
T → T+S │ S
找出句型：a(T+S)；H；(S)的短语、简单短语和句柄。
短语: a, T+S, a(T+S) , H , a(T+S);H , (S)
简单短语：a , T+S , H , (S) 句柄是 a .
6． 已知文法G[S]为：
S→AB | bC A→b | λ
B→aD | λ C→AD | b
D→aS | c
对其每一个非终级符求First集和Follow集。
First (S) = { b , a , λ }
First (A) = { b , λ }
First (B) = { a , λ }
First (C) = { b , a , c }
First (D) = { a , c }
Follow (S) = { # }
Follow (A) = { a , c , #}
Follow (B) = { # }
Follow (C) = { # }
Follow (D) = { # }
二、（10分）设有文法G[A]: A iB*e
B SB|
S [eC]|.i
C eC|
判定该文法是否为LL(1)文法。若是则给出它的LL(1)分析表，否则说明理由。
先计算各个产生式的Predict集：
Predict (A-> iB*e)={ i };
Predict (B-> SB) ={ [ , .}
Predict (B-> ) ={ * }
Predict (S->[eC]) ={ [ }
Predict (S->. i) ={ . }
Predict (C-> eC) ={ e }
Predict (C-> ) ={ ] }
因为Predict集没有冲突，所以是LL(1)文法。。