19
$\begingroup$

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!

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Ryan
    May 12 '16 at 20:09
12
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Excellent answer! Thank you a lot, this will be very useful for my PhD thesis. $\endgroup$
    – user51117
    May 12 '16 at 21:09
  • $\begingroup$ I'd check the proof if I were you, this is rather indirect. $\endgroup$
    – reinierpost
    May 13 '16 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy