World's most popular travel blog for travel bloggers.

# Algorithm for checking unambiguity in the derivation of a string

, ,
Problem Detail:

It is known that given a Context Free Grammar $G$, checking that it is ambiguous or not is undecidable. But, if I have a string $s \in L(G)$, does there exist an algorithm to check whether $s$ particularly can be derived unambiguously in $G$?

###### Answered By : Peter Leupold

gnasher's comment more or less answers this. A sketch of an algorithm would be:

• enumerate all derivations of the grammar that do not generate strings longer than $s$. This can be done, because CFGs do not have deleting rules (or if yours do, they can be converted for example to Chomsky Normal Form)
• check how many of the strings generated are equal to $s$.

This takes a long time, of course. But I doubt that there is a fundamentally better way.