《形式语言与自动机 课程小结-练习(北邮)》由会员分享，可在线阅读，更多相关《形式语言与自动机 课程小结-练习(北邮)（13页珍藏版）》请在金锄头文库上搜索。
1、Exercise 1. 给出T=a,b 上能满足下列条件的语言的文法：至少有3个a的所有符号串 a的个数不多于3的所有符号串,Exercise 2. 给出T=a 上能满足下列条件的语言的文法：L=w | |w| mod 3 =0 L=w | |w| mod 3 0 L=w | |w| mod 3 |w| mod 2 ,Exercise 3. Give a DFA accepting the following languages over the alphabet 0,1: The set of all strings such that each block of five consecut
2、ive symbols contains at least two 0s.,解答一. 记录最近读过的4个符号（不足四位时前面补足够的0）； 初态为0000； 转移规则为：去掉最左符号，当前输入符号补充为最右符号；设一个特殊状态fail，若当前状态的4个符号连同输入符号中不足两个0，则下一状态转移到fail；除fail外其它状态全是终态。 转移表如下：,解答二. 解答一中0000，0100，1000，1100可以合并为一个状态：以及0001，1001可以合并；0010,1010也可以合并；最后得到一个状态数目为11的DFA, 这是最少可能的状态数（参考DFA的最小化）。,Exercise 4.
3、Give NFA to accept the following languages. a) The set of strings over alphabet 0,1,2,3 such that the final digit has appeared before. b) The set of strings over alphabet 0,1,2,3 such that the final digit has not appeared before.,Exercise 5. Design - NFA for the following languages. Try to use - tra
4、nsitions to simplify your design. a) The set of strings consisting of zero or more as followed by zero or more bs, followed by zero or more cs. b) The set of strings consisting of either 01 repeated one or more times or 010 repeated one or more times.,Exercise 6. 写出下列语言的正则表达式: 0 的个数能够被 5 整除的所有0， 1 字
5、符串的集合.参考解答：(1*01*01*01*01*01*)* + 1*, 或 1*(01*01*01*01*0)*1*, 或 (01*01*01*01*0 + 1)*,Exercise 7. 使用状态消去技术，将如下 DFA 转化为一个正则表达式.,消去状态 q：,消去状态 r：,消去状态 s：,结果正则表达式可以为：(1+0(01+10*11)*(00+10*10)*,Exercise 8. 设计空栈接受方式的PDA，使它接受语言为所有由0,1构成的，并且任何前缀中0的个数都不少于1的个数的串的集合。参考解答：构造以空栈方式接受的PDA M = (Q, T, , , q0, Z0) ，其中
6、Q=q0，qfail ；状态q0表示当前扫描过的输入串的任何前缀中0的个数不少于1的个数，状态qfail表示当前扫描过的输入串的某个前缀中1的个数大于0的个数(即串不被接受。)；= Z0，X ；下推栈中，X的个数表示当前扫描过的输入串中0的个数比1的个数多多少；(q0,0, Z0)=( q0,X Z0), (q0,1, Z0)=( qfail, Z0)；(q0,0, X)=( q0, XX),(q0,1, X)=( q0,)；(q0, , X)=( q0, ), (q0, , Z0)=( q0, )；,Exercise 9.考虑以下两个语言：L1 = anb2ncm | n, m 0L2 =
7、anbmc2m | n, m 0a) 通过分别给出上述语言的文法来证明这些语言都是上下文无关的。b) L1L2是CFG吗？证明你的结论的正确性。参考解答：a）定义文法 G1 的产生式集合为： S AB A aAbb B cB定义文法 G2 的产生式集合为： S AB A aA B bBcc可以证明 L1=L(G1)，L2=L(G2).b）L1L2 = anb2nc4n | n 0不是CFG. 可以用Pumping引理证明之.对于任意的n，存在z =anb2nc4n 属于该语言. 令 z=w1w2w0w3w4，其中，w2w0w3 n， w2w3， 若取k=0，则 w1w2kw0w3kw4不属于该语言(分析略)，因此该语言不是CFG.,
