用于平衡括号的车床

Question

如何设计能够识别平衡括号内字符串的图灵机？例如 （（））（）。

Answer 1

要识别平衡括号的字符串，我们只需要确保没有前缀比结束括号多的结束括号，并且字符串在看到相等数目的结束括号后结束。显然，这两个条件都必须包含有效的字符串。这些是必要的要求。我将显示这些条件足以作为练习，或者无论如何，建议您对此提出一个单独的问题。

因此，我们要做的只是以下操作：

1. 从左到右读取输入
2. 在辅助磁带（如果是多磁带）上或在输入的右侧（如果是单磁带），跟踪到目前为止所看到的电流差（#open-#closed）
3. 如果差值降至零以下，则暂停->
4. 如果您到输入的末尾并且差值不为零，则暂停->
5. 如果您到输入的末尾并且差等于零，则暂停接受

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