PTT數位生活區 / Programming

[問題] FSM無法檢查任意長的括號串？

看板Programming作者 (達)時間8年前 (2016/05/31 09:27), 8年前編輯推噓3(3推 0噓 6→)
留言9則, 4人參與, 最新討論串1/1
書上看到： 我們可以造一台能將兩個任意大的數字相加的FSM，但我們無法造一台FSM來檢查任何我們 所挑選的括號串。正是這個對於無限記憶容量的要求，使我們無法製造一台FSM來執行二 進位乘法。 不太懂為什麼 FSM可以處理任意大的數字相加 卻不能處理任意長的括號串檢查 乍看之下 任意大的數字也需要無限的記憶容量 thank -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 210.65.89.53 ※ 文章網址: https://www.ptt.cc/bbs/Programming/M.1464658050.A.834.html
推
05/31 11:09, , 1F
你可以畫畫看檢查不同長度括號的FSM長甚
05/31 11:09, 1F
→
05/31 11:10, , 2F
麼樣子
05/31 11:10, 2F
推
05/31 11:58, , 3F
input的記憶體消耗不算 因為可以做成
05/31 11:58, 3F
→
05/31 11:58, , 4F
stream
05/31 11:58, 4F
→
05/31 12:08, , 5F
相加每次只要處理一位(1 digit)就好
05/31 12:08, 5F
→
05/31 12:09, , 6F
又者你有看過FSM的記憶嗎 記憶在哪裡
05/31 12:09, 6F
推
05/31 13:59, , 7F
如果你的兩個數字是分開輸入，那當然也
05/31 13:59, 7F
→
05/31 13:59, , 8F
需要無限大的記憶體
05/31 13:59, 8F
→
05/31 21:32, , 9F
那不干FSM的事情。
05/31 21:32, 9F
我好好思索下 ※ 編輯: dharma (210.65.89.53), 06/02/2016 12:34:44
‣ 更多 dharma 的文章
文章代碼(AID): #1NJEY2Wq (Programming)
Programming 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 dharma 的文章
文章代碼(AID): #1NJEY2Wq (Programming)