snippetMinor
How to check for ambiguous grammar if you don't know the string
Viewed 0 times
theknowyouambiguousgrammarforhowcheckstringdon
Problem
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?
Solution
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.
Context
StackExchange Computer Science Q#84475, answer score: 4
Revisions (0)
No revisions yet.