Cheap and Secure Web Hosting Provider : See Now

[Answers] Is it decidable whether a linear language contains a square?

, , No Comments
Problem Detail: 

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.

Asked By : Hendrik Jan

Answered By : Hendrik Jan

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

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback