一元加法的上下文无关文法

我的建议是做一个简单的起点: 1+1=11 现在,试着弄清楚如何用合法的CFG表达式来“增长”。

或者,我刚才解决了这个问题,尝试用“匹配括号”对其进行扩展,这是CFGs的一个常见介绍问题。这显然很难,但你可能会找到一条富有成效的道路。

希望这有帮助!狩猎快乐。

阿戈尔

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

前两行构成第一项和具有相同数量的一的和。构建第一个术语后,使用“A=>+1B1.“第三行构成第二项,同时向总和中添加相等数量的一。一旦完成,equals转换就完成了。

如果您将RHS改写为 1^j1^k 1 1 + 1 = 11 ,您应该能够在内部生长“j”,在外部生长“k”。

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

是的,这件事已经困扰了我一个小时了。

我也一直在做这件事,没法让它工作。这对我来说最有意义:

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

但是是的,它接受像1+111=11和11+1=111111这样的字符串和其他无意义的字符串。这里的人似乎知道但不想分享。这并不是我们可以在谷歌上搜索并得到有意义的帮助的东西。你觉得你能帮点忙吗?

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

我知道这是一个老问题,我在读戈德尔、埃舍尔、巴赫的书,也遇到了类似的问题(为pq系统生成语法)

因此,对于OP的问题,我想以下生成规则应该可以:

第一->1+秒1 | 1第一