World's most popular travel blog for travel bloggers.

Algorithm for checking unambiguity in the derivation of a string

, , No Comments
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$?

Asked By : MathManiac
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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback