pushdown-automaton - 如何确定 PDA 识别的语言

Question

我试图弄清楚如何推断 PDA 识别的语言，并且感觉我很接近，但我仍然错过了。以下面的 PDA 为例。我可以制作一个转换图来弄清楚我的增量（转换）是什么，但我从那里开始迷失了。这不是家庭作业，只是书中的一个例子。这是问题和转换表：

Answer 1

如果我正确阅读了符号，它看起来像是 L*，其中 L 是您通过只执行一次循环获得的语言。为了循环，你会看到一个“c”，一些“a”，相同数量的“b”，然后是另一个“c”。所以 L = ca^nb^nc 并且这个 PDA 的语言是 (ca^nb^nc)*。

当然，检查一下，如果我错了，请告诉我。我还可以更好地解释我试图弄清楚这一点的过程。

编辑：解释我从哪里得到 a^nb^n。

所以堆栈从堆栈底部符号Z开始。所以最初，我们处于状态 1，堆栈Z - (1, Z )。然后我们看到 ac，然后我们转换到状态 2，将 $ 压入堆栈；所以我们在 (2, $ Z )。然后假设我们连续看到 n 个 a 的实例；每次，我们都会向堆栈添加一个新的 c 并返回状态 2。因此，我们现在处于配置 (2, c^n $ Z ) 中。假设我们看到了 b 的一个实例。我们转换到状态 3 并从堆栈中删除 ac；我们现在的配置是 (3, c^(n-1) $ Z）。现在我们需要查看 b 的实例，直到我们有 $ 回到堆栈顶部；因此，在状态 3 中，我们可以看到 b 的 (n-1) 个实例，每个实例都会导致 c 的单个实例从堆栈中弹出。在看到 b 的这些实例之后，我们将处于配置 (3, $ Z ) 中。最后，我们将看到 c 的另一个实例，并且 $ 在堆栈顶部，我们可以在 (1, Z )的初始配置中弹出它并返回状态 1 。

(a^n)(b^n) 来自这样一个事实，即我们将尽可能多的 c 实例放入堆栈中，就像我们在状态 2 中看到的“a”一样，我们在状态 2 和 3 中从堆栈中删除尽可能多的实例当我们看到 b 的实例时，从堆栈中取出 c。选择 n 来表示长度是完全任意的......它仅用于指示 a 和 b 的实例数必须相同，如果我们能够看到堆栈顶部的 $ 并转换回接受状态。