作者dharma (達)
看板Programming
標題[問題] FSM無法檢查任意長的括號串？
時間Tue May 31 09:27:27 2016
書上看到：
我們可以造一台能將兩個任意大的數字相加的FSM，但我們無法造一台FSM來檢查任何我們
所挑選的括號串。正是這個對於無限記憶容量的要求，使我們無法製造一台FSM來執行二
進位乘法。
不太懂為什麼
FSM可以處理任意大的數字相加
卻不能處理任意長的括號串檢查
乍看之下
任意大的數字也需要無限的記憶容量
thank
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 210.65.89.53
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Programming/M.1464658050.A.834.html
1F：推 IKAFIRE: 你可以畫畫看檢查不同長度括號的FSM長甚 42.73.148.200 05/31 11:09
2F：→ IKAFIRE: 麼樣子 42.73.148.200 05/31 11:10
3F：推 longlongint: input的記憶體消耗不算 因為可以做成 220.137.157.92 05/31 11:58
4F：→ longlongint: stream 220.137.157.92 05/31 11:58
5F：→ MOONRAKER: 相加每次只要處理一位(1 digit)就好 60.248.110.133 05/31 12:08
6F：→ MOONRAKER: 又者你有看過FSM的記憶嗎 記憶在哪裡 60.248.110.133 05/31 12:09
7F：推 CaptainH: 如果你的兩個數字是分開輸入，那當然也 117.19.209.239 05/31 13:59
8F：→ CaptainH: 需要無限大的記憶體 117.19.209.239 05/31 13:59
9F：→ MOONRAKER: 那不干FSM的事情。 218.161.46.90 05/31 21:32
我好好思索下
※ 編輯: dharma (210.65.89.53), 06/02/2016 12:34:44