<p>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.</p>

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

<p>REFERENCES</p>

<p>[1] N. Chomsky and M. P. Schützenberger, The Algebraic Theory of Context-Free Languages, Computer Programming and Formal Systems, 1963.</p>

CC BY-SA 4.0
2018-06-20T06:20:02.803Z
indeed, thank @EmilJeřábek for spotting this
Lorenzo
CC BY-SA 4.0
2018-06-15T08:42:14.490Z
2018-06-20T06:19:08.743Z
2018-06-20T06:19:08.743Z
Lorenzo
<p>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 <em>unambiguous</em> 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? </p>

<p>I find this problem a little intriguing, since it is known that equivalence is decidable for <em>deterministic</em> 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. </p>

CC BY-SA 3.0
2017-07-18T15:36:00.747Z
Inclusion is undecidable: https://pdfs.semanticscholar.org/afdb/faff0f6024f06d92ef4757df11e9324ea7ca.pdf
Peter Leupold
CC BY-SA 3.0
2017-07-19T07:10:01.770Z
@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...
Jára Cimrman
CC BY-SA 3.0
2017-07-19T07:11:09.740Z
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.
Jára Cimrman
<fl.formal-languages><grammars><context-free><decidability><undecidability>
Is equivalence of unambiguous context-free languages decidable?
Jára Cimrman
# Is equivalence of unambiguous context-free languages decidable?

(Asked by: username_0 on 2017-07-11)

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.

**Tags:** fl.formal-languages, grammars, context-free, decidability, undecidability
> **Comments:**
> **username_1**: Inclusion is undecidable: https://pdfs.semanticscholar.org/afdb/faff0f6024f06d92ef4757df11e9324ea7ca.pdf  
> **username_0**: @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...  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_2 on 2018-06-15. Score: 10 | Accepted answer

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.

> **Comments:**
> **username_2**: indeed, thank @EmilJeřábek for spotting this  

---

