4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.)

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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.