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

Question

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

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

Answer 1

第一个可能会像这样工作:

1. 读取第一个状态的a并将a压入堆栈；过渡到新状态
2. 读取第二状态下的b，并将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 都设计为当堆栈为空并且输入耗尽时在接受状态下接受。