computer-science - 图灵机用于平衡括号

Question

如何设计一个可以识别平衡括号串的图灵机？例如 （（））（）。

Answer 1

要识别平衡括号的字符串，我们只需要确保没有前缀的右括号比左括号多，并且字符串在看到相同数量的左括号和右括号后结束。显然，这两个条件都必须包含有效的字符串；这些都是必要的要求。我会留下这些条件作为练习就足够了，或者无论如何，建议你就此提出一个单独的问题。

所以，我们需要做的就是以下几点：

1. 从左到右读取输入
2. 在辅助磁带（如果是多磁带）或输入右侧（如果是单磁带）上，跟踪目前看到的当前差异（#open - #close）
3. 如果差值低于零，则停止拒绝
4. 如果您到达输入的末尾并且差异不为零，则停止拒绝
5. 如果到达输入的末尾并且差值为零，则停止接受

假设是单磁带 TM，您可以读取一个符号，然后用一些标记覆盖它，然后根据您看到的是左括号还是右括号，移动到磁带的末尾；然后，在末尾添加一个新符号（如果打开）或从末尾删除一个（如果关闭）；然后，进入一个新的状态，回到第一个未标记的输入符号，并重复。