一元加法的上下文无关语法
给定一个 1 的字母表，我想解析以下形式的加法：
1^k + 1^j = 1^k+j
这很容易用下推自动机来表示，只需将前两个 1 中的每一个 1 压入堆栈，然后弹出最后一组 1 即可。然而，我似乎无法弄清楚如何将其表示为上下文无关语法，这显然是可能的，因为 PDA == CFG。
Given an alphabet of 1s I want to parse addition of the form
1^k + 1^j = 1^k+j
This is pretty easy to represent with a pushdown automaton simply by pushing a 1 on to the stack on each of the first two 1s, and then popping on the last set of 1s. However, I can't seem to figure out how to represent this as a context free grammar, which is obviously possible since PDA == CFG.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
前两行构造第一项和具有相同数量的总和。第一项构建完成后，您可以使用“A => +1B1”进入第二项。第三行构造第二项，同时将相同数量的 1 添加到总和中。完成后，等于转换将完成它。
请注意，这不允许表达式中的任何项等于零。此外，您可以构造稍有变化的一元减表达式，请记住 a - b = c 相当于 a = b + c
The first two rows construct the first term and the sum with the same number of ones. Once the first term is constructed, you move onto the second with "A => +1B1." The third row constructs the second term, simultaneously adding an equal number of ones to the sum. Once you're done, the equals transition finishes it up.
Note that this doesn't allow any term in the expression to equal zero. Also, you can construct unary minus expressions with a slight variation, keeping in mind that a - b = c is equivalent to a = b + c
如果您将 RHS 重写为
1^j1^k，那么您应该会看到它只是两个嵌套的平衡1集。结合1 + 1 = 11的“基本情况”，您应该能够增大内部的“j”和外部的“k”。If you rewrite the RHS as
1^j1^k, then you should see it's just two nested sets of balanced1s. Combined with a "base case" of1 + 1 = 11, you should be able to grow the "j"s on the inside and the "k"s on the outside.使用上下文无关语法或下推自动机不可能进行通用一元加法。对于这种类型的计算，您必须使用图灵机。编写将 1 压入堆栈的下推自动机是无效的，因为堆栈实际上并不是 PDA 的输出。 PDA 的唯一输出是二进制“接受”或“拒绝”，其指示输入字符串是否是 PDA 识别的语言的一部分。
Generic unary addition not possible with a context free grammar or with a pushdown automaton. For this type of computation you must use a Turing Machine. Writing a pushdown automaton that pushes 1's onto the stack is not valid because the stack is not really the output of a PDA. The only output of a PDA is a binary "Accept" or "Reject" which indicates whether or not the input string is a part of the language that is recognized by the PDA.
我的建议是做一个简单的起点：
1+1=11
现在尝试弄清楚如何使用合法的 CFG 表达式“增长”它。
或者，我刚才通过尝试用“匹配括号”来扩展它来解决这个问题，这是 CFG 的常见介绍问题。这显然更难，但你可能会找到一条富有成效的道路。
希望这有帮助！狩猎快乐。
阿戈尔
My advice is to make a simple starting point:
1+1=11
And now try to figure out how you can "grow" that with legal CFG expressions.
Alternatively, I solved this just now by trying to extend it with "matching parenthesis", which is a common introduction problem to CFGs. Its obviously harder, but you may find a fruitful path that way.
Hope this helps! Happy hunting.
Agor
是的，这个问题在过去一小时里一直困扰着我。
另外，cdiggins, 1 + 1 = 111 会通过
Yeah, this one has been bothering me for the past hour.
Also, cdiggins, 1 + 1 = 111 would pass that
我也一直在研究这个问题，但无法让它发挥作用。这对我来说最有意义：
A -> B + B = BB
B-> BB
B-> 1
但是，是的，它接受 1 + 111 = 11 和 11 + 1 = 111111 等字符串以及其他无意义的字符串。似乎这里的人都知道但不愿意分享。这并不是我们可以通过谷歌搜索并获得有意义的帮助的东西。您认为您可以提供更多帮助吗？
i have been workin on this forever also and cant get it to work. this is what makes most sense to me:
A -> B + B = BB
B -> BB
B -> 1
but yea, this accepts strings like 1 + 111 = 11 and 11 + 1 = 111111 and other nonsense. seems like people here know but don't feel like sharing. this isnt exactly something we can google and get meaningful help. think you could be slightly more helpful?
我知道这是一个老问题，我正在阅读哥德尔、埃舍尔、巴赫，并被类似的问题（为其 pq 系统生成语法）所困扰。
所以对于OP的问题，我想以下产生式规则应该这样做：
首先 - > > 1+秒1 | 1第1
第二-> 1 = 1 | 1秒1
I know its an old question, I was reading Godel, Escher, Bach and was struck on similar problem (of generating a grammer for its pq system)
So for the OP's question, I guess the following production rules should do:
first -> 1+second1 | 1first1
second -> 1=1 | 1second1