computer-science - 一元加法的上下文无关语法

Question

给定一个 1 的字母表，我想解析表格的添加

1^k + 1^j = 1^k+j

这很容易用下推自动机表示，只需在前两个 1 中的每一个上将 1 压入堆栈，然后在最后一组 1 上弹出。但是，我似乎无法弄清楚如何将其表示为上下文无关语法，这显然是可能的，因为 PDA == CFG。

score 4 · Accepted Answer

S => 1A1
A => 1A1 | +1B1
B => 1B1 | =

前两行构造第一项和具有相同数量的总和。一旦构造了第一项，您就可以使用“A => +1B1”进入第二项。第三行构造第二项，同时将相等数量的 1 添加到总和中。完成后，equals 转换完成它。

请注意，这不允许表达式中的任何项等于零。此外，您可以构造稍有变化的一元减号表达式，请记住 a - b = c 等价于 a = b + c

score 2 · Accepted Answer

如果您将 RHS 重写为1^j1^k，那么您应该会看到它只是两个嵌套的平衡1s 集。结合的“基本情况” 1 + 1 = 11，您应该能够在内部增长“j”，在外部增长“k”。

score 2 · Accepted Answer

使用上下文无关语法或下推自动机不可能进行通用一元加法。对于这种类型的计算，您必须使用图灵机。编写将 1 压入堆栈的下推自动机是无效的，因为堆栈实际上并不是 PDA 的输出。PDA 的唯一输出是二进制“接受”或“拒绝”，它指示输入字符串是否是 PDA 识别的语言的一部分。

score 1 · Accepted Answer

我的建议是做一个简单的起点：1+1=11 现在试着弄清楚如何使用合法的 CFG 表达式“发展”它。

或者，我刚刚通过尝试使用“匹配括号”来扩展它来解决这个问题，这是 CFG 的常见引入问题。它显然更难，但你可能会找到一条富有成效的道路。

希望这可以帮助！狩猎愉快。

亚戈尔

score 0 · Accepted Answer

0

S   ->  1 + 1 = 11
S   ->  1S1
S   ->  1 + 1A11
A   ->  1 = 1
A   ->  1A1

于 2012-10-11T00:02:08.517 回答

score 0 · Accepted Answer

是的，这个问题在过去的一个小时里一直困扰着我。

此外， cdiggins, 1 + 1 = 111 会通过

score 0 · Accepted Answer

我知道这是一个老问题，我正在阅读 Godel、Escher、Bach 并且遇到了类似的问题（为其 pq 系统生成语法）

因此，对于 OP 的问题，我想应该遵循以下生产规则：

第一 -> 1+第二1 | 1 前 1 秒 -> 1=1 | 1秒1

score 0 · Accepted Answer

我也一直在努力解决这个问题，但无法让它发挥作用。这对我来说最有意义：

A -> B + B = BB B -> BB B -> 1

但是，是的，它接受像 1 + 111 = 11 和 11 + 1 = 111111 这样的字符串和其他废话。似乎这里的人知道但不想分享。这不是我们可以通过谷歌搜索并获得有意义帮助的东西。认为您可以提供更多帮助？

8 回答 8