lili对《Introduction to the Theory of Computation》的笔记(1)

Introduction to the Theory of Computation
  • 书名: Introduction to the Theory of Computation
  • 作者: Michael Sipser
  • 页数: 456
  • 出版社: Cengage Learning
  • 出版年: 2005-2-15
  • 第83页
    对于83页1.4题的答案。 请大家看看是否正确。
    原题:

    e.原文有误应为:"{w|w has an even number of a's and has at most one b}"


    f.要求奇数个a,并且以a,b结尾。解题中并没有用奇数个a的DFA,于以a,b结尾的DFA相交。因为第一个图有奇数个a,在加上以a,b结尾。会导致偶数个a于要求不符。所以用个偶数个a的DFA和以a,b结尾的DFA相交,不知到符合题目要求不.

    g.由于题目要求长度为偶数,a为奇数,所以可知两图的交DFA中b也为奇数。

    答案不一定正确。也不一定时最优的。请大家指正。
    2011-07-09 16:16:37 6回应