HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to check for ambiguous grammar if you don't know the string

Submitted by: @import:stackexchange-cs··
0
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.