作者dharma (达)
看板Programming
标题[问题] FSM无法检查任意长的括号串？
时间Tue May 31 09:27:27 2016
书上看到：
我们可以造一台能将两个任意大的数字相加的FSM，但我们无法造一台FSM来检查任何我们
所挑选的括号串。正是这个对於无限记忆容量的要求，使我们无法制造一台FSM来执行二
进位乘法。
不太懂为什麽
FSM可以处理任意大的数字相加
却不能处理任意长的括号串检查
乍看之下
任意大的数字也需要无限的记忆容量
thank
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 210.65.89.53
※ 文章网址: https://webptt.com/cn.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