如何设计 NPDA 来接受这些语言？

Question

我想设计接受以下两种语言的PDA（非确定性下推自动机）。 请解释如何设计它们。

L(r) where r = abb*aba*
L(r) = {a^nb^2n : n > 0}

Answer 1

第一个可能是这样工作的：

1. 在第一个状态读取一个a并将一个a压入堆栈；过渡到新状态
2. 在第二个状态下读取a b并将a b压入堆栈；过渡到新状态
3. 永远在第三种状态下读取b，每次都将b压入栈中。如果你最终读取了一个 a，转换到一个新的状态并将一个 a 压入堆栈
4. 在第四状态读取b，将b压入栈中；过渡到新状态
5. 永远以第五状态读取a，将a压入堆栈；在任何时候，不确定地过渡到新状态
6. 在第六种状态下，什么也不读，然后从堆栈中弹出东西。此状态正在接受并且 npda 接受输入字符串当且仅当输入已被完全读取且堆栈为空。

第二个可能是这样工作的：

1. 读取至少一个a并将其压入堆栈，然后转换到新状态
2. 在第二种状态下一直读a，每次压一个a入栈；如果你看到 b，去一个新的状态
3. 在第三种状态下读取b，将a弹出栈；进入新状态
4. 在第四种状态下读取b，不去管栈；回到第三状态
5. 在第三和第四状态继续读取 b，直到你 运行 没有输入；如果你处于第四种状态，运行 没有输入并且有一个空堆栈，然后 pda 才接受输入字符串

编辑：所需转换的概述。

第一个：

q0 is initial
(q0, a, Z) -> (q1, aZ)
(q1, b, a) -> (q2, ba)
(q2, b, b) -> (q2, bb)
(q2, a, b) -> (q3, ab)
(q3, b, a) -> (q4, ba)
(q4, a, b) -> (q4, ab)
(q4, a, a) -> (q4, aa)
(q4, e, a) -> (q5, a)
(q4, e, b) -> (q5, b)
q5 is accepting

第二个：

q0 is initial
(q0, a, Z) -> (q1, aZ)
(q1, a, a) -> (q1, aa)
(q1, b, a) -> (q2, a)
(q2, b, a) -> (q3, e)
(q3, b, a) -> (q2, a)
q3 is accepting

两个NPDA都设计成在栈为空输入耗尽时在接受状态接受。