# Is language equality for linear context-free grammars decidable?

Let's consider two context-free grammars $G_1$ and $G_2$ and ask the following question: Is $L(G_1) = L(G_2)$, that is, are the two grammars equivalent?

In general, this problem is undecidable. However, if both $G_1$ and $G_2$ are left-linear (or right-linear) grammars, then the problem is decidable, because both grammars describe regular languages.

My question is whether or not the same problem is decidable when both grammars are linear. Also, if anybody can point to relevant literature, that will be highly appreciated!

• I proved as a TA this semester that $ALL_{LG}$ is undecidable for general linear grammars (public.asu.edu/~ccolbou/src/555hw3extras16sol.pdf, Question 3). It's just a straightforward reduction to the equality problem. – Ryan May 12 '16 at 20:09

This refers to Baker, B. S. and Book, R. V. (1974), Reversal-bounded multipushdown machines, J. Comput. System Sci. 8, 315-332, which, in the proof of that Lemma 1, presents a subset of linear context-free languages such that deciding whether a member of the set is equal to $\Sigma^*$ is equivalent to deciding the Post Correspondence Problem.