# 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.

• Inclusion is undecidable: pdfs.semanticscholar.org/afdb/… Jul 18 '17 at 15:36
• @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... Jul 19 '17 at 7:10
• 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. Jul 19 '17 at 7:11