平时作业
1 对于下列语言分别写出它们的正规表达式。
(1) 英文字母组成的所有符号串，要求符号串中顺序包含五个元音。
答： 令Letter表示除这五个元音外的其它字母。
  ((letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter))*
(2) 英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。
答： A*B*....Z*
(3) Σ={0,1}上的含偶数个1的所有串。
答： (0|10*1)*
(4) Σ={0,1}上的含奇数个1的所有串。
答：(0|10*1)*1
(5) 具有偶数个0和奇数个1的有0和1组成的符号串的全体。
答：设S是符合要求的串，|S|=2k+1 (k≥0）。
则 S→S10|S21，|S1|=2k (k>0），|S2|=2k (k≥0）。
且S1是{0,1}上的串，含有奇数个0和奇数个1。
 S2是{0,1}上的串，含有偶数个0和偶数个1。   
考虑有一个自动机M1接受S1，那么自动机M1如下：
和L(M1)等价的正规表达式，即S1为：
((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*
类似的考虑有一个自动机M2接受S2，那么自动机M2如下：
和L(M2)等价的正规表达式，即S2为：
((00|11)|(01|10)(00|11)*(01|10))*
因此，S为：   
((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*0|
((00|11)|(01|10)(00|11)*(01|10))*1
(6) 不包含子串011的由0和1组成的符号串的全体。
答：1*|1*0(0|10)*(1|ε)
(7) 由0和1组成的符号串,把它看成二进制数，能被3整除的符号串的全体。
答： 假设w的自动机如下：
对应的正规表达式：(1(01*0)1|0)*
2 给出接受下列在字母表{0,1}上的语言的DFA。
(1) 所有以00结束的符号串的集合。
(2) 所有具有3个0的符号串的集合。
答：
(1) DFA M=({0，1}，{q0，q1，q2}，q0，{q2}，δ)
其中δ定义如下:
δ（q0，0）=q1    δ（q0，1）=q0
δ（q1，0）=q2    δ（q1，1）=q0
δ（q2，0）=q2    δ（q2，1）=q0
(2)正则表达式: 1*01*01*01*
DFA M=({0，1}，{q0，q1，q2，q3}，q0，{q3}，δ)
其中δ定义如下:
δ（q0，0）=q1    δ（q0，1）=q0
δ（q1，0）=q2    δ（q1，1）=q1c语言编译器怎么用文件格式提交作业
δ（q2，0）=q3    δ（q2，1）=q2
δ（q3，1）=q3   
3 下面是用正规式表示的变量声明：
        ( int | float ) id (, id )* ;
请改用上下文无关文法表示，也就是写一个上下文无关文法，它和该正规式等价。
答：D  T L ;
      T  int | float
    L  L, id | id
4 试分析下面给出的if-then-else语句的文法，它的提出原本是为了矫正dangling-else (悬而未决的-else)文法的二义性：
stmt → if expr then stmt
|matched-stmt
matched-stmt→ if expr then matched-stmt else stmt
|other
试说明此文法仍然是二义性的。
答：考虑句子if e then if e then other else if e then other else other 它具有如下所示的两种分析树 stmt expr then e if stmt if matched-stmt expr then matched-stmt e other if esle stmt matched-stmt expr then matched-stmt e other esle stmt matched-stmt other stmt matched-stmt if expr then matched-stmt e if esle stmt esle stmt matched-stmt expr then e stmt other expr then matched-stmt e other if matched-stmt other
则上面给出的if-then-else文法仍是二义性的。
5 证明下面文法是SLR(1)文法，并构造其SLR分析表。
E→E+T|T
T→TF|F
F→F*|a|b
答：该文法的拓广文法G'为
(0) E' → E
(1) E → E+T
(2) E → T
(3) T → TF
(4) T → F
(5) F → F*
(6) F → a
(7) F → b
其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:
I0 = {E'→·E, E→·E+T, E→·T, T→·TF, T→·F, F→·F*,        F→·a, F→·b} 
I1 = {E'→E·, E→E·+T}I2 = {E→T·, T→T·F, F→·F*, F→·a, F→·b}
I3 = {T→F·, F→F·*}    I4 = {F→a·}    I5 = {F→b·} 
I6 = {E→E+·T, T→·TF, T→·F, F→·F*, F→·a, F→·b}  I7 = {T→TF·, F→F·*}  I8 = {F→F*·}
I9 = {E→E+T·, T→T·F, F→·F*, F→·a, F→·b}
求FOLLOW集：    FOLLOW(E)={＋, ＄}    FOLLOW(T)={＋, ＄, a, b}
FOLLOW(F)={＋, ＄, a, b, *}
构造的SLR分析表如下：
显然，此分析表无多重定义入口，所以此文法是SLR文法。
6 为下面的文法构造LALR(1)分析表
S→E
E→E+T|T
T→(E)|a
答：其拓广文法G'：
(0) S' → S
(1) S → E
(2) E → E+T
(3) E → T
(4) T → (E)
(5) T → a
构造其LR(1)项目集规范族和goto函数(识别活前缀的DFA)如下:
I0 = {[S’→·S, $], [S→·E, $], [E→·E+T, $/+], [E→·T, $/+], [T→·(E), $/+], [T→·a, $/+]}
I1 = {[S’→S·, $]}    I2 = {[S→E·, $], [E→E·+T, $/+]}    I3 = {[E→T·, $/+]}
I4 = {[T→(·E), $/+], [E→·E+T, )/+], [E→·T, )/+],  [T→·(E), )/+], [T→·a, )/+]}
I5 = {[T→a·, $/+]}    I6 = {[E→E+·T, $/+], [T→·(E), $/+], [T→·a, $/+]}
I7 = {[T→(E·), $/+], [E→E·+T, )/+]}      I8 = {[E→T·, )/+]}
I9 = {[T→(·E), )/+}, [E→·E+T, )/+], [E→·T, )/+], [T→·(E), )/+], [T→·a, )/+]}
I10 = {[T→a·, )/+]}  I11 = {[E→E+T·, $/+]}  I12 = {[T→(E)·, $/+]}
I13 = {[E→E+·T, )/+], [T→·(E), )/+], [T→·a, )/+]}    I14 = {[T→(E·), )/+], [E→E·+T, )/+]}
I15 = {[E→E+T·, )/+]}    I16 = {[T→(E)·, )/+]}