如何获得PDA的转换关系？

问题描述：

我知道如何弄清楚开始状态，接受状态，输入字母和所有东西。但你如何发展PDA的过渡关系？对于FSM，（q0，a），q1）表示如果从q0开始并得到a，则转换到q1。但是（S，a，e），（S，a）是什么意思？（S是开始状态，e是epsilon）如何获得PDA的转换关系？

答

而不是（S，a，e），（S，a）中应该是底部符号（看起来像颠倒的T）的ε。稍后我会解释这一点。

第一个S就是你现在所处的状态。这对应于FSM中的q0。

a是您阅读的符号，与FSM中的a相同。请注意，当你得到一个和而不是一个这意味着你是在你的字符串的末尾，没有什么可读的。

主要区别在于下一个字母，在这种情况下是e。这表示当您阅读a时位于堆栈顶部的单个堆栈符号。从技术上讲，你永远不会读空栈。在计算机中，这与读取空内存相同，但它不能完成。这是因为堆栈的“底部”包含一个表示您位于底部的符号。传统上，这是使用颠倒的T（底部符号）表示的。

第二个括号中的S表示您将要进入的状态，就像FSM中的q1一样。

最后，第二个括号中的a是要添加到堆栈上的符号（或符号）。每当你从栈中读取某些东西（每次发生转换时），该符号都会从堆栈中移除。然后，你可以把一个新的符号或几个新的符号放到堆栈上，或者你可以不加任何东西（e）。当你刚刚阅读底部符号时，什么都不说，意味着你已经完成了，并且你接受了字符串（如果接受空栈）。你也可以通过最终状态来接受，但空的堆栈更简单一些。

我会告诉你一个简单的例子，PDA {a^n b^n | n> = 0}。我们的字母显然是{a，b}，我们需要2个状态（一个用于a部分，另一个用于b部分），我们称它们为{p，q}。我们会让p成为我们的开始状态。我们的堆栈字母表，我们可以放到堆栈上的符号是{bottom，A}。 Bottom总是堆栈字母表的一部分，每当我们得到一个a（并且每当我们得到一个b时弹出一个），我们会将A推入堆栈。让我们接受空堆栈，这意味着当我们读取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.

注意，有过渡不允许的，如之前的任何一个的得到一个b。通过不包括它们，需要它们的字符串不被接受。希望这可以帮助！

如何获得PDA的转换关系？

相关推荐