如何确定 PDA 识别的语言
我试图弄清楚如何推断 PDA 可以识别什么语言，感觉自己已经很接近了，但仍然错过了。以下面的PDA为例。我可以制作一个转换图来弄清楚我的增量（转换）是什么，但我从那里开始迷失了。这不是作业，只是书中的一个例子。这是问题和转换表：
Im trying to figure out how to deduce what language a PDA recognizes, and feel like im close but am still missing out. Take the following PDA for example. I can make a transition chart to figure out what my delta (transitions) are but im lost from there on out. This isnt a homework assignment, just an example from the book. Heres the problem and the transition table:
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（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 中，我们可以看到 (n-1) 个 b 实例，每个实例都会导致从堆栈中弹出一个 c 实例。看到 b 的这些实例后，我们将处于配置 (3, $ Z) 中。最后，我们将看到 c 的另一个实例，并且 $ 位于堆栈顶部，我们可以将其弹出并移回状态 1，即 (1, Z) 的初始配置。
(a^n)(b^n) 来自这样的事实：我们将与状态 2 中看到的“a”一样多的 c 实例放入堆栈，并且在状态 2 和 3 中从堆栈中删除与状态 2 和 3 一样多的实例当我们看到 b 的实例时，c 从堆栈中出来。选择 n 来表示长度是完全任意的...它仅用于指示 a 和 b 的实例数必须相同，如果我们能够看到堆栈顶部的 $ 并转换回接受状态。
If I'm reading the notation correctly, it looks like it's L*, where L is the language you get by doing the loop once only. To go round the loop, you see a "c", some number of "a", the same number of "b", then another "c". So L = ca^nb^nc and the language of this PDA is (ca^nb^nc)*.
Naturally, check this and please tell me if I'm wrong. I can also explain better the process I went throug to try to figure this out.
EDIT: Explaining where I get a^nb^n from.
So the stack starts out with only the bottom-of-the-stack symbol Z. So initially, we're in state 1 with stack Z - (1, Z). We then see a c, and we transition to state 2, pushing a $ onto the stack; so we are in (2, $ Z). Then let's say we see n instances of a in a row; each time, we will add a new c to the stack and return to state 2. Therefore, we are now in configuration (2, c^n $ Z). Let's say we then see an instance of b. We transition to state 3 and remove a c from the stack; our configuration is now (3, c^(n-1) $ Z). Now we need to see instances of b until we have $ back on top of the stack; so, in state 3, we can see (n-1) instances of b, each of which will cause a single instance of c to be popped from the stack. After seeing these instances of b, we will be in configuration (3, $ Z). Finally, we will see another instance of c and, $ being on top of the stack, we can pop it and move back to state 1, in our initial configuration of (1, Z).
The (a^n)(b^n) comes from the fact that we put as many instances of c onto the stack as we see 'a' in state 2, and we remove from the stack in states 2 and 3 as many instances of c from the stack as we see instances of b. The choice of n to represent the length is completely arbitrary... it's only used to indicate that the number of instances of a and b must be the same, if we are able to see the $ on top of the stack and transition back to the accepting state.