[問題] 單紙帶圖靈機與 o(n log n)

看板Prob_Solve作者 ( )時間14年前 (2011/11/08 23:22), 編輯推噓3(3推 0噓 6→)
留言9則, 4人參與, 最新討論串1/1
課本上有一題是說：任何可以被單紙帶圖靈機在 o(n log n) 時間內 recognize 的語言皆為 regular，但是沒有任何提示，實在想不到該如何下手。 請問能不能提示一下？ 在網路上搜尋也沒有找到資料，除了找到別人的 homework ...: http://www.cs.au.dk/~arnsfelt/CT08/homework/homework1.pdf -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.115.144.99 ※ 編輯: suhorng 來自: 59.115.144.99 (11/08 23:28)
推
11/08 23:56, , 1F
This theorem is proved by Kobayashi, which is not an
11/08 23:56, 1F
→
11/08 23:56, , 2F
easy result. This may be helpful to you:
11/08 23:56, 2F
→
11/08 23:56, , 3F
11/08 23:56, 3F
推
11/09 08:32, , 4F
某本書收集了很多很難的問題... xD
11/09 08:32, 4F
→
11/09 21:36, , 5F
感謝一樓:) 用至這個當關鍵字搜尋到神奇的東西:
11/09 21:36, 5F
→
11/09 21:36, , 6F
11/09 21:36, 6F
→
11/09 21:36, , 7F
2010final_sol.pdf
11/09 21:36, 7F
→
11/09 21:37, , 8F
裡面 Problem 5 是這題並有解答...
11/09 21:37, 8F
推
11/16 22:05, , 9F
老師出這題當期末考的時候全班沒人做出來
11/16 22:05, 9F
‣ 更多 suhorng 的文章
文章代碼(AID): #1EkKb2UL (Prob_Solve)