http://wiki.apidesign.org/wiki/Impossible
我看了一下这个，我不明白为什么这个问题似乎是不可能的。给“机器”的字符串总是有限的吧？
因此，即使我有 10 亿个零和 10 亿个零，也可以轻松编写一个脚本，为该字符串返回 true 或 false（它将是 true/接受）。
另一个输入可能是“00011”，这使其无效。
我可能在这里不明白什么，但这个问题对我来说似乎是“可编码的”。
1 回答
0
当您说“可编码”时，您的意思是它可以使用可以被视为图灵机版本（隐含无限内存）的计算机进行编码。但是有限状态机没有无限的内存（比如 10 亿个状态），当它们被输入 10 亿个和 1 个零时，它们会忘记零的数量（忘记）并且无法将其与相同数量的 1 匹配。可以使用常规语言的泵引理来建立一个完整的论点： http ://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages
于 2015-04-03T14:47:59.357 回答