我怎么能证明这个语法是不明确的？

S -> bA|aB 
A -> a|aS|bAA 
B -> b|bS|aBB

任何简单的方法，而不是试图找到一个字符串，会产生两个分析树？我怎么能证明这个语法是不明确的？

有人可以给我一个可以证明这一点的字符串。

来源

2011-02-02 crowso

对我来说这看起来像它明确。 – crowso 2011-02-02 18:53:02

请允许我欢迎您来到StackOverflow，并提醒我们通常在这里做的三件事：1）当您获得帮助时，尝试给予它**在您的专业领域回答问题** 2）[阅读常见问题] http://tinyurl.com/2vycnvr）3）当你看到很好的问答时，把它们投票[`使用灰色三角形]（http://i.imgur.com/kygEP.png），作为系统基于用户通过分享知识获得的声誉。还记得接受更好地解决你的问题的答案，如果有的话，['通过按复选标记]（http://i.imgur.com/uqJeW.png） – 2011-02-02 18:56:16

有没有简单的方法来证明上下文无关语法模糊 - 实际上， the question is undecidable，通过减少到Post correspondence problem。

来源

2011-02-02 18:56:52

是的，但我不能在答题纸上写下。我应该看看哪些语法属性来正确选择产生2个解析树的字符串？ – crowso 2011-02-03 03:47:54

有一个字符串，但：bbaaba

S -> bA -> bbAA -> bbaA -> bbaaS -> bbaabA -> bbaaba 
S -> bA -> bbAA -> bbaSA -> bbaaBA -> bbaabA -> bbaaba

来源

2013-03-24 22:08:05 Shweta

我怎么能证明这个语法是不明确的？

回答

相关问题