如何获取上下文无关语法及其对应的PDA？
我不明白如何解决这个练习。
我需要制作一个上下文无关语法来验证以下输入：
L={w € (0,1,2)* | w= 2^n 0^(m+1) 1^(m+n) with n>=0, m>0}
如何创建相应的 PDA？
我认为该语言没有前缀属性，因此 PDA 无法接受空堆栈。 对吗？
I can't understand how can I solve this exercise.
I need to make a context-free grammar that can validate the following input :
L={w € (0,1,2)* | w= 2^n 0^(m+1) 1^(m+n) with n>=0, m>0}
How can I create the corresponding PDA?
I think that the language doesn't have prefix-property so the PDA can't accept by empty stack.
Is it right?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我们先来试试语法；然后我们将为它制作一个自动机。
在制作 CFG 时（实际上是任何语法，包括正则表达式），了解该语法可以轻松实现的几种简单语言会很有帮助。上下文无关语法可以很容易地完成常规语法可以做的任何事情，而且它还可以匹配输入。这意味着像 a^nb^n、回文、匹配括号等语言很容易做到。
当考虑这样的问题时，尝试看看这些刻板语言中的哪一种（如果有的话），您的语言中的全部或部分字符串是什么样的。在这种情况下，我们似乎对 a^nb^n 有一个变体；我们需要执行两次才能完成加法。
让我们从 0^(m+1) 1^m 开始。我们可以为此制作一个 CFG 吗？嗯，当然；它实际上与 a^nb^n 相同。就是这样：
现在我们需要解决 n 项：我们应该能够在左侧添加 2，在右侧添加 1，数量相等。这也很简单：
就是这样。要获得 CFG，您可以根据这些东西的定义轻松构建自下而上或自上而下的解析器。我们将尝试从头开始制作一款 PDA。
我们的 PDA 需要在循环中接受 2，并将每个 2 压入堆栈。毕竟，我们需要记住我们看到了多少。当我们看到 0 时，我们应该进入一个新状态，并继续在循环中接受 0，为输入中看到的每个 0 添加一个 0 到堆栈中。当我们看到 1 时，我们应该进入一个新状态，并在循环中接受 1，从堆栈中删除 2 或 0。如果实现细节正确，您将能够以与前三个不同的接受状态接受空堆栈。
Let's first try the grammar; then we'll make an automaton for it.
When making a CFG - any grammar, really, including regular expressions - it's helpful to know a few kinds of simple languages that the grammar could easily do. Context free grammars can pretty easily do anything a regular grammar can, and it can also match inputs. This means languages like a^n b^n, palindromes, matched parentheses, etc. are easy to do.
When looking at a problem like this, try to see which of these stereotypical languages, if any, all or part of strings in your language look like. In this case, it appears we have a variation on a^n b^n; we need to do this twice to accomplish the addition.
Let's start out with 0^(m+1) 1^m. Can we make a CFG for this? Well, sure; it's practically the same as a^n b^n. Here it is:
Now we need to address the n term: we should be able to add 2 to the left and 1 to the right, in equal number. This is also easy:
There you go. To get a CFG, you can easily build a bottom-up or top-down parser, according to the definition of these things. We'll try to make a PDA from scratch.
Our PDA needs to accept 2 in a loop, pushing each 2 on the stack. We will need to remember how many we saw, after all. When we see a 0, we should go to a new state, and keep accepting 0 in a loop, adding a 0 to the stack for each 0 seen in input. When we see a 1, we should go to a new state, and accept 1 in a loop, removing either 2 or 0 from the stack. If you get the implementation details right, you will be able to accept with empty stack in an accepting state separate from the first three.