我知道如何弄清楚开始状态、接受状态、输入字母表以及所有这些东西。但是你如何开发PDA的过渡关系呢？对于 FSM，(q0,a),q1) 意味着如果您从 q0 开始并获得 a，则您过渡到 q1。但是 (S,a,e),(S,a) 是什么意思？（S 是开始状态，e 是 epsilon）
1 回答
0
而不是 (S,a,e),(S,a) 中的 epsilon 应该是底部符号（看起来像倒置的 T）。我稍后会解释这一点。
第一个 S 就是你现在所处的状态。这对应于 FSM 中的 q0。
a是您阅读的符号，与 FSM 中的a相同。请注意，当你得到一个e而不是a时，这意味着你在你的字符串的末尾，没有什么可读的了。
主要区别在于下一个字母，在本例中为e。这表示当您读取a时位于堆栈顶部的单个堆栈符号。但是从技术上讲，您永远无法读取空堆栈。在计算机中，这与读取空内存相同，只是无法完成。这是因为堆栈的“底部”包含一个表示您位于底部的符号。传统上，这使用倒置的 T（底部符号）来表示。
第二个括号中的 S 表示您将要进入的状态，就像 FSM 中的 q1 一样。
最后，第二个括号中的a是您要添加到堆栈中的符号（或符号）。每次您从堆栈中读取某些内容（即每次发生转换）时，该符号都会从堆栈中删除。然后，您可以将一个新符号或几个新符号放入堆栈，或者您可以什么都不放 (e)。当您刚刚阅读底部符号时，什么都不放意味着您已经完成，并且您正在接受字符串（如果通过空堆栈接受）。您也可以按最终状态接受，但空堆栈要简单一些。
我给你看一个简单的例子，一个 PDA 用于 {a^nb^n | n >= 0}。我们的字母表显然是 {a,b}，我们需要 2 个状态（一个用于a部分，一个用于b部分），我们称它们为 {p,q}。我们将让p成为我们的开始状态。我们的堆栈字母表，我们可以放入堆栈的符号将是 {bottom,A}。底部始终是堆栈字母表的一部分，每次获得 a 时我们都会将 A 压入堆栈（每次获得a b时都会弹出一个）。让我们通过空堆栈来接受，这意味着当我们将e作为符号并将底部作为堆栈符号读取时，如果我们没有将任何内容放回堆栈，那么我们已经接受了该字符串。我们的增量转换如下：
(p,e,bottom),(p,e) //this is an accepting state for a^0 b^0
(p,a,bottom),(p,A bottom) //we read an a and we're at the bottom of the stack, we add an A to the stack and put back the bottom symbol below it.
(p,a,A),(p,AA) //we read an A off the stack and an *a* in our string, we put back the A we read from the stack and add another one
(p,b,A),(q,e) //we read an A off the stack and a *b*, so we go to our state q, and don't add anything to the stack.
(q,b,A),(q,e) //every time we get a *b* and there's an A on the stack, remove it
(q,e,bottom),(q,e) //this is an accepting state, as we've canceled out all the a's with b's and we're done reading our string.
请注意，有些转换是不允许的，例如在任何 a 之前获得a b。如果不包括它们，则不接受需要它们的字符串。希望这可以帮助！
于 2013-12-20T19:17:59.140 回答