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$?

  • $\begingroup$ I imagine that most parsing algorithms can be adapted to keep track of this information. $\endgroup$ – Yuval Filmus Sep 18 '16 at 15:45
  • 1
    $\begingroup$ I suppose Earley's algorithm would easily find all derivations, except you'd have problems if there are too many. Finding that there are at least two derivations would be about as simple as finding there is at least one. $\endgroup$ – gnasher729 Sep 18 '16 at 17:26

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.

  • $\begingroup$ Nice answer! This is a clean way to see that the problem is decidable. Incidentally, while the question didn't ask for it, there is even an efficient algorithm for the problem; see my answer. (This is exponential time; my answer sketches how to do it polynomial time.) $\endgroup$ – D.W. Oct 6 '16 at 17:00

The CYK algorithm can be modified in a straightforward way to solve this problem. In particular, the problem is not only decidable -- there is a reasonably efficient algorithm to solve it.

The standard CYK algorithm uses dynamic programming to compute $P[i,j,X]$, a boolean that indicates whether $s[i..j]$ is a member of $L(X)$, for each pair of indices $i,j$ and each non-terminal $X$. I suggest you also compute $Q[i,j,X]$, which indicates whether $s[i..j]$ can be derived unambiguously from $X$. It is easy to adjust the recursion to compute both $P$ and $Q$ simultaneously.

This achieves a $O(n^3 \cdot |G|)$ running time, i.e., polynomial time.

You can probably do the same with Earley parsing or any method of GLR parsing.


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.