# context free grammar for palindrome: $L_n = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$

Let $$L_{n} = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$$

Generate a cfg of $$L_n$$

For n = 1, 2, 3

Informally, x is in $$L_n$$ means some palindrome of at least length n is a substring of x that occurs exactly at the midpoint of x.

for $$n = 1$$

$$S \to 0S0 | 1S1 | 0S1 | 1S0|0 | 1 | 00 | 11$$

for $$n = 2$$

$$S \to 0S0 | 1S1 | 0S1 | 1S0 | 0A0 | 1A1$$

$$A \to 0 | 1 | \epsilon$$

for $$n = 3$$

$$S \to 0S0 | 1S1 | 0S1 | 1S0 | 0A0 | 1A1$$

$$A \to 0 | 1 | 00 | 11 | \epsilon$$

would this be right?

Say I changed it to $$|y| > |z|$$ or $$|y| < |z|$$ how would this differ?

• This CFG doesn't generate $001 \in L_1$. – Yuval Filmus Nov 12 '18 at 8:07
• What don't you understand? What would you like us to explain? What level should an answer be written at? – David Richerby Nov 12 '18 at 13:31

When $$n=1$$, the language $$L_1$$ consists of all words of the form $$ywz$$, where $$|y|=|z|$$ and $$w$$ is a non-empty palindrome. We can generate all non-empty palindromes as follows: $$P \to 0P0 \mid 1P1 \mid 0 \mid 1 \mid 00 \mid 11$$ Given that, we can generate $$L_1$$ by capturing also the outer part: $$S \to 0S0 \mid 0S1 \mid 1S0 \mid 1S1 \mid P$$ For larger $$n$$, all we need to change is the "base cases" for $$P$$.
Further observation reveals that we can actually assume that $$|w| \leq 2$$ (for $$n = 1$$), and so we can use alternatively the following productions for $$P$$: $$P \to 0 \mid 1 \mid 00 \mid 11$$ This allows us to eliminate $$P$$ from the grammar, reaching the following grammar: $$S \to 0S0 \mid 0S1 \mid 1S0 \mid 1S1 \mid 0 \mid 1 \mid 00 \mid 11$$ These steps can also be extended to larger $$n$$.