我怎么能证明这种语法是模棱两可的? [英] how can i prove that this grammar is ambiguous?

问题描述

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

除了试图找到一个会生成两个解析树的字符串之外，还有其他简单的方法吗?

Any easy method other than trying to find a string that would generate two parse trees ?

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

Can someone please give me a string that can prove this.

推荐答案

没有简单的方法可以证明上下文无关的语法不明确-实际上， 通过简化为问题无法确定 .org/wiki/Post_correspondence_problem"rel =" noreferrer>帖子对应问题.

There is no easy method for proving a context-free grammar ambiguous -- in fact, the question is undecidable, by reduction to the Post correspondence problem.

这篇关于我怎么能证明这种语法是模棱两可的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！