pushdown-automaton - 使用JFLAP做下推自动机的方法

Question

我需要使用识别以下语言的 JFLAP 创建下推自动机：

需要采取哪些步骤来做到这一点？它是如何工作的？

Answer 1

我认为这个问题更适合cs.stackexchange.com，但无论如何我都会添加我的解决方案。

形成一个例子

它实际上比看起来更容易，让我们考虑一个例子，我们的出现有以下值：

n = 2
m = 3
p = 1

这应该允许我们形成以下字符串：

a ² b ³ c ¹ a ¹⁺³ b ² = aabbbcaaaabb

形成逻辑理解

由此我们需要确定我们需要跟踪哪些符号。

1. 我们知道外部符号会出现n多次，n,m ≥ 1因此我们需要跟踪n此处并且要求它至少出现一次。
2. 我们知道q = p+m并且至少m也会发生，所以我们需要跟踪.m
3. 如果q = p+m我们还需要保留一个发生，p但是注意那个p也不能发生，因为它声明了p ≥ 0。

形成正式的定义

我们让我们的 PDA P成为以下 PDA：

P = (Q, Σ, Γ, τ, q ₀ , Z, q ₆ )

在哪里：

• Q 是我们的 d-PDA 中的状态集
• Σ 是包含字符串的输入符号
• Γ 是包含集合 Γ = {a,b} 的堆栈符号
• q ₀是我们的初始（开始）状态
• Z 是我们的堆栈符号#
• q ₆是我们的最终（结束）状态

形成下推自动机

因此，由此我们可以形成以下自动机（在 JFLAP 中）：

所以在这里，我们只是跟踪上面提到的符号，但这里需要注意的重要一点是q3，转换为c0或更多的转换。

我们还使用符号#作为堆栈符号。

模拟

如果我们使用上面指定的输入来模拟这个 PDA ( aabbbcaaaabb)，我们会得到以下结果：