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| &gt; |z|$ or $|y| &lt; |z|$ how would this differ?
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$.