形式语言与自动机 课程小结-练习(北邮).ppt

《形式语言与自动机 课程小结-练习(北邮).ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、Exercise1.给出T={a,b}上能满足下列条件的语言的文法：至少有3个a的所有符号串a的个数不多于3的所有符号串Exercise2.给出T={a}上能满足下列条件的语言的文法：L={w

2、

3、w

4、mod3=0}L={w

5、

6、w

7、mod3>0}L={w

8、

9、w

10、mod3<>

11、w

12、mod2}Exercise3.GiveaDFAacceptingthefollowinglanguagesoverthealphabet{0,1}:Thesetofallstringssuchthateachblockoffiveconsecutivesymbolscontainsatleasttwo0’s.解答一.

13、记录最近读过的4个符号（不足四位时前面补足够的0）；初态为0000；转移规则为：去掉最左符号，当前输入符号补充为最右符号；设一个特殊状态fail，若当前状态的4个符号连同输入符号中不足两个0，则下一状态转移到fail；除fail外其它状态全是终态。转移表如下：解答二.解答一中0000，0100，1000，1100可以合并为一个状态：以及0001，1001可以合并；0010,1010也可以合并；最后得到一个状态数目为11的DFA,这是最少可能的状态数（参考DFA的最小化）。Exercise4.GiveNFAtoacceptthefollowinglanguages.a)Thesetofstr

14、ingsoveralphabet{0,1,2,3}suchthatthefinaldigithasappearedbefore.b)Thesetofstringsoveralphabet{0,1,2,3}suchthatthefinaldigithasnotappearedbefore.Exercise5.Design-NFAforthefollowinglanguages.Trytouse-transitionstosimplifyyourdesign.a)Thesetofstringsconsistingofzeroormorea’sfollowedbyzeroormoreb’s,

15、followedbyzeroormorec’s.b)Thesetofstringsconsistingofeither01repeatedoneormoretimesor010repeatedoneormoretimes.Exercise6.写出下列语言的正则表达式:0的个数能够被5整除的所有0，1字符串的集合.参考解答：(1*01*01*01*01*01*)*+1*,或1*(01*01*01*01*0)*1*,或(01*01*01*01*0+1)*Exercise7.使用状态消去技术，将如下DFA转化为一个正则表达式.消去状态q：消去状态r：消去状态s：结果正则表达式可以为：(1+0(0

16、1+10*11)*(00+10*10))*Exercise8.设计空栈接受方式的PDA，使它接受语言为所有由0,1构成的，并且任何前缀中0的个数都不少于1的个数的串的集合。参考解答：构造以空栈方式接受的PDAM=(Q,T,Γ,δ,q0,Z0)，其中Q={q0，qfail}；状态q0表示当前扫描过的输入串的任何前缀中0的个数不少于1的个数，状态qfail表示当前扫描过的输入串的某个前缀中1的个数大于0的个数(即串不被接受。)；Γ={Z0，X}；下推栈中，X的个数表示当前扫描过的输入串中0的个数比1的个数多多少；δ(q0,0,Z0)={(q0,XZ0)},δ(q0,1,Z0)={(qfail,

17、Z0)}；δ(q0,0,X)={(q0,XX)},δ(q0,1,X)={(q0,)}；δ(q0,,X)={(q0,)},δ(q0,,Z0)={(q0,)}；Exercise9.考虑以下两个语言：L1={anb2ncm

18、n,m≥0}L2={anbmc2m

19、n,m≥0}a)通过分别给出上述语言的文法来证明这些语言都是上下文无关的。b)L1∩L2是CFG吗？证明你的结论的正确性。参考解答：a）定义文法G1的产生式集合为：SABAaAbbBcB定义文法G2的产生式集合为：SABAaABbBcc可以证明L1=L(G1)，L2=L(G2).b）L1∩L2={anb

20、2nc4n

21、n≥0}不是CFG.可以用Pumping引理证明之.对于任意的n，存在z=anb2nc4n属于该语言.令z=w1w2w0w3w4，其中，w2w0w3n，w2w3，若取k=0，则w1w2kw0w3kw4不属于该语言(分析略)，因此该语言不是CFG..