如何构造 L={a^nb^m where n<=m<=2n} 的下推自动机？
How to construct a pushdown automata for L={a^nb^m where n<=m<=2n}?
应该不用2叠来建造。我试过了，但没有 2 层我做不到。
策略是这样的：我们可以很容易地制作一个接受 a^n b^n 的 PDA，也可以很容易地制作一个接受 a^n b^2n 的 PDA。我们的语言是这些语言的超集，它也接受任何 b 在 n 和 2n 之间的数字。我们可以利用非确定性来允许这一点，如下所示：对于我们放入堆栈的每个 a，我们可以非确定性地决定在弹出 a 之前是消耗一个还是两个 b。如果我们的NPDA选择每次消费一个，我们得到a^n b^n。如果它选择每次消耗两个，我们得到a^n b^2n。如果它选择两者中的一些，我们会得到介于这些极端之间的数字 b。我们仅在用空堆栈耗尽输入时才接受。
Q s S Q' S' Comment
q0 e e qA e Allow empty string to be accepted
q0 a x q0 ax Count a and push onto stack
q0 e x q1 x Transition to counting b
q1 b ax q1 x Mark off a single b for each a
q1 b ax q2 x Mark off the first of two b for this a
q1 e e qA e Allow string in language to be accepted
q2 b x q1 x Mark off the second of two b for this a
在这个 PDA 中，我们将 q0 作为初始状态，将 qA 作为接受状态。在 aabbb 处理：
q0, aabbb, e
-> q0, abbb, a
-> q0, bbb, aa
-> q1, bbb, aa
-> q1, bb, a
-> q2, b, e
-> q1, e, e
-> qA, e, e
当然有很多解析不会导致 qA，但在 NPDA 中，如果至少有一个，我们会接受。
此图像包含此语言的图形下推自动机
应该不用2叠来建造。我试过了，但没有 2 层我做不到。
策略是这样的：我们可以很容易地制作一个接受 a^n b^n 的 PDA，也可以很容易地制作一个接受 a^n b^2n 的 PDA。我们的语言是这些语言的超集，它也接受任何 b 在 n 和 2n 之间的数字。我们可以利用非确定性来允许这一点，如下所示：对于我们放入堆栈的每个 a，我们可以非确定性地决定在弹出 a 之前是消耗一个还是两个 b。如果我们的NPDA选择每次消费一个，我们得到a^n b^n。如果它选择每次消耗两个，我们得到a^n b^2n。如果它选择两者中的一些，我们会得到介于这些极端之间的数字 b。我们仅在用空堆栈耗尽输入时才接受。
Q s S Q' S' Comment
q0 e e qA e Allow empty string to be accepted
q0 a x q0 ax Count a and push onto stack
q0 e x q1 x Transition to counting b
q1 b ax q1 x Mark off a single b for each a
q1 b ax q2 x Mark off the first of two b for this a
q1 e e qA e Allow string in language to be accepted
q2 b x q1 x Mark off the second of two b for this a
在这个 PDA 中，我们将 q0 作为初始状态，将 qA 作为接受状态。在 aabbb 处理：
q0, aabbb, e
-> q0, abbb, a
-> q0, bbb, aa
-> q1, bbb, aa
-> q1, bb, a
-> q2, b, e
-> q1, e, e
-> qA, e, e
当然有很多解析不会导致 qA，但在 NPDA 中，如果至少有一个，我们会接受。
此图像包含此语言的图形下推自动机