[Solved]: Is language equality for linear context-free grammars decidable?

ignougroup
Problem Detail: 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!

Asked By : Agent Gotse

Answered By : reinierpost

Quoting from Amiram Yehudai, The Decidability of Equivalence for a Family of Linear Grammars, Information and Control 47, 122-136 (1980), page 1:

The equivalence problem for various families of languages is of great interest in the theory of formal languages. This problem is decidable for regular languages (Rabin and Scott, 1959) and undecidable for context-free languages (Bar-Hillel et al., 1961). It is also undecidable for the family of linear context-free languages, as follows from Lemma 1 in (Baker and Book, 1974). The family of uniform linear languages is a natural and nontrivial subfamily of the linear languages for which equivalence is decidable.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/57377