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.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Inclusion is undecidable: pdfs.semanticscholar.org/afdb/… $\endgroup$
    – Peter Leupold
    Jul 18, 2017 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, 2017 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, 2017 at 7:11

1 Answer 1

Reset to default
10
$\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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ indeed, thank @EmilJeřábek for spotting this $\endgroup$
    – Lorenzo
    Jun 20, 2018 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.