如何用图灵机验证两个符号的比率？

Question

我有一个模块的作业：

为这种语言制作一个图灵机：

{𝑤 ∈ {𝑎,𝑏}* | 2(𝑤中𝑎的数量) = 3(𝑤中𝑏的数量)}.

如何确保维持该比率？如果我们可以检查每 5 个数字是否由 3 个

a

和 2 个

b

组成（例如，对于输入

aababaabab

），我可以看到如何检查这一点，但是对于像

aaaaaabbbb

这样的单词，我不知道看看如何处理它，因为组合的数量很快就会变得巨大。

Answer 1

我假设这意味着比率 n/m = 3/2，其中 n 是 a 出现的次数，m 是 b 出现的次数。

为了解决一般情况，可以有很多解决方案；这是一个可能很容易理解的。

1. 从左到右扫描，找到 3 次出现 a。跳过 A、B 和 b。将找到的三个 a 更改为 A，然后返回到磁带的开头。如果您到达磁带末尾而没有越过任何 a 或 b，则停止-接受。如果您在磁带末尾看到了一些 a 和 b 但至少没有看到三个 a，则停止-拒绝。否则，继续步骤 2。
2. 从左到右扫描，找到 2 次出现 b。跳过 A、B 和 a。将找到的两个 b 更改为 B 并返回到磁带的开头。如果你到达终点时没有看到至少两个 b，则停止-拒绝。重复从步骤 1 开始，直到您停止接受或停止拒绝。

示例：

aababaabab    aaaaaabbbb     aaaaabbbb
AAbAbaabab    AAAaaabbbb     AAAaabbbb
AABABaabab    AAAaaaBBbb     AAAaaBBbb
AABABAAbAb    AAAAAABBbb     halt_reject
AABABAABAB    AAAAAABBBB
halt_accept   halt_accept

Answer 2

当要求a的个数的2倍等于b的个数的3倍时，a的个数必须是3的倍数，b的个数必须是偶数。这个我们可以先检查一下。这样做时，我们可以“擦除”（就像使用字符“#”）三个“a”中的两个（在向前扫描中）和两个“b”中的一个（在向后扫描中）。

如果这两个条件中的任何一个为假，我们就可以拒绝输入。

否则，那么在剩下的部分中，我们应该检查“a”和“b”有多少个。在将“a”与“b”（无论顺序）匹配时，我们可以清除当前输入开头的任何“#”，这样我们就不会浪费不必要的时间来扫描同一部分。

这是该方法的转换表：

状态	阅读	写	摇头	下一个状态
a0	a	#	对	a1
a0	b		对	a0
a0	_		左	b0
a1	a	#	对	a2
a1	b		对	a1
a1	_		左	拒绝
a2	a		对	a0
a2	b		对	a2
a2	_		左	拒绝
b0	a 或#		左	b0
b0	b	#	左	b1
b0	_		对	匹配00
b1	a 或#		左	b1
b1	b		左	b0
b1	_		对	拒绝
匹配00	#	_	对	匹配00
匹配00	a	_	对	比赛10
匹配00	b	_	对	比赛01
匹配00	_		左	接受
比赛10	# 或 a		对	比赛10
匹配10	b	#	对	比赛11
比赛10	_		左	拒绝
比赛01	# 或 b		对	比赛01
比赛01	a	#	左	比赛11
比赛01	_		左	拒绝
比赛11	#、a 或 b		左	比赛11
比赛11	_		对	匹配00

这是一个您可以使用自己的输入运行的实现：

createTuring({
    transitions: [
        // Number of "a" must be multiple of 3, keep only one out of three
        { state: "a0",    read: "a", write: "#", move: "R", nextState: "a1"     },
        { state: "a0",    read: "b",             move: "R", nextState: "a0"     },
        { state: "a0",    read: "_",             move: "L", nextState: "b0"     },
        { state: "a1",    read: "a", write: "#", move: "R", nextState: "a2"     },
        { state: "a1",    read: "b",             move: "R", nextState: "a1"     },
        { state: "a1",    read: "_",             move: "L", nextState: "reject" },
        { state: "a2",    read: "a",             move: "R", nextState: "a0"     },
        { state: "a2",    read: "b",             move: "R", nextState: "a2"     },
        { state: "a2",    read: "_",             move: "L", nextState: "reject" },
        // Number of "b" must be multiple of 2, keep only one out of two
        { state: "b0",    read: "a#",            move: "L", nextState: "b0"     },
        { state: "b0",    read: "b", write: "#", move: "L", nextState: "b1"     },
        { state: "b0",    read: "_",             move: "R", nextState: "match00" },
        { state: "b1",    read: "a#",            move: "L", nextState: "b1"     },
        { state: "b1",    read: "b",             move: "L", nextState: "b0"     },
        { state: "b1",    read: "_",             move: "R", nextState: "reject" },
        // Match the number of "a" and "b" that remain
        { state: "match00", read: "#", write: "_", move: "R", nextState: "match00" },
        { state: "match00", read: "a", write: "_", move: "R", nextState: "match10" },
        { state: "match00", read: "b", write: "_", move: "R", nextState: "match01" },
        { state: "match00", read: "_",             move: "L", nextState: "accept"  },
        { state: "match10", read: "#a",            move: "R", nextState: "match10" },
        { state: "match10", read: "b", write: "#", move: "R", nextState: "match11" },
        { state: "match10", read: "_",             move: "L", nextState: "reject"  },
        { state: "match01", read: "#b",            move: "R", nextState: "match01" },
        { state: "match01", read: "a", write: "#", move: "L", nextState: "match11" },
        { state: "match01", read: "_",             move: "L", nextState: "reject"  },            
        { state: "match11", read: "#ab",           move: "L", nextState: "match11" },
        { state: "match11", read: "_",             move: "R", nextState: "match00" },
    ],
    initState: "a0",
    tape: "abaaabbbbaabaabaaaab",
});

<script src="https://trincot.github.io/turing.js"></script>