“下推自动机”的设计识别语言：a^nb^m | n≤m≤3n

Question

我正在学习自动机考试和正式语言，我必须设计一个能够识别该语言的 PDA：

a^n b^m | n<= m <= 3n

我有一个小小的想法，但我坚持这一点：

首先思考处理所有“a”和每个“a”推“A”

(q0, a, Z)= (q0, AZ)
(q0, a, A)= (q0, AA)
(q0, b, A)= (q1, A)
(q1, b, A)= (q2, A)
(q2, b, A)= (q3, lambda)
(q3, b, A)= (q1, A)
(q3, lambda, A)= (qf, Z)
(q3, lambda, Z)= (qf, Z)

qf = final state, lambda= delete top of stack, Z= initial symbol of the stack

所以我想到了解决方案，但我认为不正确，我做错了什么？

Answer 1

是的，您的自动机不正确，因为它不接受字符串 ab 或空字符串。您将获得以下机器状态序列：

- q0 Z
a q0 AZ
b q1 AZ
(doesn't accept)

- q0 Z
(doesn't accept)

由于 q1 不接受，因此您的机器无法接受 ab，它采用您所描述的语言。

您的总体思路是正确的：为您看到的每个 a 添加一个 A，然后为您看到的每组 1、2 或 3 个 b 删除一个 A。这个公式显然是不确定的，但我们假设这是可以的，除非需要 DPDA。

(q0, a, Z) => (q0, AZ)
(q0, a, A) => (q0, AA)
(q0, -, Z) => (q1, Z)
(q0, -, A) => (q1, A)

这些转换对 A 进行计数并将 A 添加到堆栈中。读完 a 后，我们可以进入下一个状态 q1，并开始计算 b 并弹出 A。

(q1, -, A) => (q2, A)
(q1, -, A) => (q3, A)
(q1, -, A) => (q4, A)

这些转换允许机器不确定地选择是否对特定 A 计数 1、2 或 3 个 b。

(q2, b, A) => (q1, -)

(q3, b, A) => (q5, A)
(q5, b, A) => (q1, -)

(q4, b, A) => (q6, A)
(q6, b, A) => (q7, A)
(q7, b, A) => (q1, -)

这些转换实际上处理计数 1、2 或 3 个 b 并删除 A，返回到 q1 以允许删除额外的A 来自堆栈。

(q1, -, Z) => (qf, Z)

一旦 A 堆栈耗尽，此转换允许 PDA 接受字符串。请注意，如果输入上有任何 b 剩余，PDA 将在 qf 中崩溃，因为那里没有定义任何转换；由于它崩溃了，所以该字符串不被接受（即使堆栈是空的并且它在接受状态下崩溃）。

解决这个问题的另一种方法是为该语言构造一个CFG，然后构造一个自上而下或自下而上的解析器。这种语言的一个简单的 CFG 是：

S := aSb | aSbb | aSbbb

如果需要 DPDA，那么这是一个更难的问题，并且答案可能是“不存在 DPDA”。说实话，我还没有考虑过为这种语言构建 DPDA。

Answer 2

我知道这有点晚了，但我遇到了同样的问题，我想如果有一个不同的解决方案，所以基本的想法是你将堆栈划分为 3 个分区，其中

• 第一个分区具有以下属性：(size = n，character = 'A')
• 第二个分区：(size = 2n ，character = 'B')
• 第三个分区：(size = n ，character = 'A')

最上面的分区 - 第三个分区 - 其目的是确保乙的count 至少等于 a 的计数 -n- ，中间分区 -第二个 - 是为了确保 b 的计数小于或等于 2n ，最后一个分区是为了确保 b 的计数不超过 2n ；所以这是基本思想，当然它是一个 NPDA，这是确切的转换：

(q0 , a , #) => (q0 , A#)
(q0 , a , A) => (q0 , AA)
(q0 , a , B) => (q0 , AB)
(q0 , b , A) => (q0 , BA)
(q0 , b , B) => (q0 , BB)
(q0 , lambda , A) => (q0 , AA)
(q0 , lambda , B) => (q0 , AB)
(q0 , lambda , B) => (q0 , BB)
(q0 , lambda , A) => (q0 , BA)
(q0 , b , A) => (q1 , match) >> -match means removing the top of the stack with the current element-

现在我们转到 q1 以确保 b 的计数至少等于 a 的计数：

(q1 , b , A) => (q1 , match)
(q1 , # , B) => (qf , -) >> -this means that i matched equal number of a's and b's and i can halt if there is no more input-
(q1 , b , B) => (q2 , match)

现在我们转到 q2 以确保b 的计数小于或等于 2n ：

(q2 , b , B) => (q2 , match)
(q2 , # , A) => (qf , -)
(q2 , # , B) => (qf , -)