19
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Inclusion is undecidable: pdfs.semanticscholar.org/afdb/… $\endgroup$ – Peter Leupold Jul 18 '17 at 15:36
  • 4
    $\begingroup$ @PeterLeupold Yes, but inclusion is undecidable for deterministic context-free languages as well, so this is quite straightforward (the article that you link to just gives a proof without using this fact). However, equivalence seems to be much more interesting, since this is decidable for deterministic context-free languages and undecidable for general context-free languages... $\endgroup$ – Jára Cimrman Jul 19 '17 at 7:10
  • 3
    $\begingroup$ Nevertheless, I start to suspect that this problem might be open: a proof of decidability is hardly known, since the one for deterministic CFLs is quite complicated; on the other hand, undecidability would imply undecidability of equivalence of $\mathbb{N}$-algebraic series in noncommutative variables, which, if I understood everything properly, should be an open problem. $\endgroup$ – Jára Cimrman Jul 19 '17 at 7:11
9
$\begingroup$

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. Schützenberger, The Algebraic Theory of Context-Free Languages, Computer Programming and Formal Systems, 1963.

$\endgroup$
  • 2
    $\begingroup$ I think you mean inherently ambiguous languages. $\endgroup$ – Emil Jeřábek Jun 15 '18 at 11:08
  • $\begingroup$ indeed, thank @EmilJeřábek for spotting this $\endgroup$ – Lorenzo Jun 20 '18 at 6:20

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.