Theoretical Computer Science
fl.formal-languages grammars context-free decidability undecidability
Updated Sun, 22 May 2022 03:16:57 GMT

Is equivalence of unambiguous context-free languages decidable?


It is well known that the equivalence problem is undecidable for general context-free languages. However, all proofs of this fact that I am aware of seem to involve some ambiguous context-free grammars. For this reason, I would like to ask if it is known whether the problem remains undecidable while restricting oneself to unambiguous context-free languages. That is, given two context-free grammars that are a priori granted to be unambiguous, is it decidable whether they are equivalent or not?

I find this problem a little intriguing, since it is known that equivalence is decidable for deterministic context-free languages, though this result is far from trivial... On the other hand, there might be some simple reason for undecidability that I have been overlooking.




Solution

This is currently an open problem. As correctly pointed out, if it is decidable, then one expects the proof to be hard since it generalises the famous DPDA equivalence problem. On the other hand, the classical arguments for undecidability of the CFL universality problem make use of inherently ambiguous languages, and thus one needs new ideas to show undecidability.

Let me point out that the universality problem for UCFLs is decidable (in PSPACE), using generating functions [1].

REFERENCES

[1] N. Chomsky and M. P. Schtzenberger, The Algebraic Theory of Context-Free Languages, Computer Programming and Formal Systems, 1963.





Comments (1)

  • +0 – indeed, thank @EmilJeábek for spotting this — Jun 20, 2018 at 06:20