# Is it decidable whether a linear language contains a square?

A square is a word of the form $ww$. A linear grammar is a CFG that has productions of the form $A\to uBv$ or $A\to u$ (with lower case symbols corresponding to terminal strings).

Question: Is it decidable whether a linear grammar generates a square?

What did I do? I know that it is undecidable whether a linear grammar contains a palindrome, and that it is undecidable that a context-free grammar contains a square. Both via reduction from PCP. Given two sequences $(u_1,\dots, u_n)$ and $(v_1,\dots, v_n)$, strings of the form $u_{i_1}\dots v_{i_k}\#v_{i_k}\dots u_{i_k}$ are linear, whereas those of the form $i_1\dots i_k u_{i_1}\dots u_{i_k}\#j_1\dots j_k v_{j_1}\dots v_{j_k}\#$ are context free.

It is indeed undecidable whether a linear grammar generates a square. Same technique, reduction from PCP.

Starting with the two sequences of strings $(u_1,\dots,u_n)$, $(v_1,\dots,v_n)$ that define the PCP we can build a linear grammar with strings of the form $u_{i_1}\dots u_{i_k} j_k \dots j_1 \# v_{j_1}\dots v_{j_k} i_k \dots i_1 \#$.

Rules like $S\to A\#$;

$A \to u_i A i \mid u_i B i$;

$B \to j A v_j \mid j v_j$.

Such a string is a square if both the indices and the strings match, hence iff we generate a solution of PCP.

(I really did not know the answer when I posted the question... Sorry. I started examining ways to show decidability.)

• Indices and strings have to be encoded using disjoint alphabets, right? Otherwise looking good. – Raphael Mar 30 '16 at 20:48
• Indeed that is assumed. Alternatively add another set of $\#$ to separate the parts. – Hendrik Jan Mar 30 '16 at 22:23
• Of course! That's not silly at all. Self-answering is good practice (if it's done in the right way); see here. – Raphael Mar 31 '16 at 5:49