现给出一个NFA:M=(Σ,Q,0,{9},f) 其中Σ={羊，空，菜，狼} Q={0,1,2,3,4,5,6,7,8,9}
转换函数
f(0,羊)=1, f(1,空)=2, f(2,菜)=3, f(2,狼)=5, f(3,羊)=4 f(5,羊)=6, f(4,狼)=7, f(6,菜)=7, f(7,空)=8, f(8,羊)=9
37、 简单描述由下面的产生式对应的文法生成的语言： S→aA A→bS S→?
Answer： S?aA?abS?abaA?ababS 由此可得， L(G)={(ab)n：n≥0}
38、 在∑={a，b}上构造接受下面语言的DFA： L={ w：|w| mod 3 = 0}
Answer：
使用标记为|w| mod 3的状态，则解是：
39、 在∑={0，1}上，构造接受下列语言的DFA：
每个00后面都紧跟着1的符号串。如101，0010，0010011001都属于这种语言，而0001和00100不属于。
Answer： 对连续的0的个数进行计数，从而得到DFA的主要部分：
然后加入其他转换以处理连续的0，并为不可能接受的符号串设置陷井(trap)。
40、 找到一个DFA，识别所有前缀为ab，定义在∑={a，b}上的符号串。
这里需要考虑的只有符号串的前两个符号；读入这两个符号后，符号串余下的部分就不必理会了。因此，我们设计一个四状态的自动机来解决这个问题。这四个状态分别是：初态、两个识别ab并最终进入终态的状态，和一个非终态的陷井状态。
如果第一个符号是a，第二个符号是b，那么自动进入终态。而且，不管剩下的输入是什么，它都会停留在这个状态中。另外，如果第一个符号不是a，或者第二个符号不是b，那么自动进入非终态的陷井状态中。
41、 给出句型F+T*F的短语、直接短语和句柄
Answer：
短语：F，T*F，F+T*F 直接短语：F，T*F 句柄：F
42、 给出句型E+T*i的短语，直接短语和句柄
Answer：
短语：i，T*i，E+T*i 直接短语：i 句柄：i
43、 已知文法： S?aAB A?bBb B?A|?
给出符号串abbbb的最左推导和最右推导。 最左推导是：
S?aAB?abBbB?abAbB?abbBbbB?abbbbB?abbbb 最右推导是：
S?aAB?aA?abBb?abAb?abbBbb?abbbb
44、 文法G[S]为： S?Ac|aB A?ab B?bc
该文法是否为二义的？为什么？ [答案]
对于串abc
(1) S=>Ac=>abc (2) S=>aB=>abc
即存在两不同的最右推导，所以该文法是二义的。
45、 文法G[S]为： S?Ac|aB A?ab B?bc
写出L(G[S])的全部元素。 [答案]
S=>Ac=>abc 或S=>aB=>abc 所以L(G[S])={abc}
46、 设计一个接受语言L((a|b)*b(a|bb)*)的NFA
47、 已知Σ={a，b，c}，构造L的正则表达式： L={w：|w| mod 3 = 0}
产生所有长度为3的符号串并重复。解为： ((a|b|c)(a|b|c)(a|b|c))*
48、 包含偶数个0的0、1串。
产生两个0，中间填入一些1，然后重复。但要记住，一个0都没有的情况。解为： (1*01*01*)*|1*
49、
三、 分析题
1、 证明下面文法：
S?AaAb|BbBa A?? B??
是LL(1)文法，但不是SLR(1)文法。
Answer：
(1) 因为仅非终结符S有两个不同的选择，只考虑S的两个右部，由于
First(AaAb) = {a} First(BbBa) = {b}
First(AaAb) ∩ First(BbBa) = φ 所以该文法为LL(1)文法。 (2) 由于
Follow(AaAb) = {a，b} Follow(BbBa) = {a，b}
First(AaAb) ∩ First(BbBa) ≠ φ
对任何句子，在面临第一个符号时的空规则中，不知道应该将?规约为A还是B，存在归约-归约冲突，因而不是SLR(1)文法。
2、 设有正规式r=1(0|1)*101，试给出：
(a) 识别该正规集的NFA；
(b) 识别该正规集的DFA并最简化(要有计算过程)；