Let's say I have a CFG grammar $G$ which describes some rules for language generation. How can you tell that grammar can generate ambiguous results for a string if you don't know that string? I know how to check for ambiguity when you're given a particular string but what about the cases when it's not? Is there any algorithm to do this?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
You cannot tell that a context-free grammar is ambiguous, since the problem is undecidable. This can be proved by a straightforward reduction from the Post correspondence problem, for example. What this means is that there is no algorithm that, given a context-free grammar, decides whether it is ambiguous or not.
answered Nov 26, 2017 at 12:24
$\begingroup$
$\endgroup$
1
My answer is this, you can not check for ambiguity if no string is given, because there is no algorithm till now to check for ambiguity.
-
4$\begingroup$ What's the difference from the existed answer? $\endgroup$– xskxzrCommented Apr 14, 2019 at 11:32