3
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.