Jtdylktuy

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?

Everything here is assuming $Sigma={0,1}$.

Your solution for $n=1$ and $n=2$ are correct, but $n=3$ is not quite right because it allows $11$ and $00$ which are not in $L_3$. To fix this, simply remove $epsilon$ from the rule for $A$. The following solution, while verbose, scales well for any $n$.

The rule $A_i$ will be the rule that produces every palindrome of length $i$ or $i-1$. For $ige3$, $$
A_ilongrightarrow 0A_{i-2}0text{ }|text{ }1A_{i-2}1text{ }|text{ }0A_{i-3}0text{ }|text{ }1A_{i-3}1
$$
Let
$$
A_2longrightarrow 0text{ }|text{ }1text{ }|text{ }00text{ }|text{ }11 \
A_1longrightarrow epsilontext{ }|text{ }0text{ }|text{ }1 \
A_0longrightarrow epsilon
$$

Then any $L_n$ can be produced by the rules for $A_0, A_1, ..., A_n, A_{n+1}$ and starting symbol $S$ with rule$$
Slongrightarrow 0S0text{ }|text{ } 0S1text{ }|text{ }1S0text{ }|text{ }1S1text{ }|text{ }A_{n+1}
$$

For $n=1$, we can write,
$$
Slongrightarrow 0S0text{ }|text{ } 0S1text{ }|text{ }1S0text{ }|text{ }1S1text{ }|text{ }A_2 \
A_2longrightarrow 0text{ }|text{ }1text{ }|text{ }00text{ }|text{ }11 \
A_1longrightarrow epsilontext{ }|text{ }0text{ }|text{ }1 \
A_0longrightarrow epsilon
$$

For $n=2$, we can write,
$$
Slongrightarrow 0S0text{ }|text{ } 0S1text{ }|text{ }1S0text{ }|text{ }1S1text{ }|text{ }A_3 \
A_3longrightarrow 0A_{1}0text{ }|text{ }1A_{1}1text{ }|text{ }0A_{0}0text{ }|text{ }1A_{0}1 \
A_2longrightarrow 0text{ }|text{ }1text{ }|text{ }00text{ }|text{ }11 \
A_1longrightarrow epsilontext{ }|text{ }0text{ }|text{ }1 \
A_0longrightarrow epsilon
$$

For $n=3$, we can write,
$$
Slongrightarrow 0S0text{ }|text{ } 0S1text{ }|text{ }1S0text{ }|text{ }1S1text{ }|text{ }A_4 \
A_4longrightarrow 0A_{2}0text{ }|text{ }1A_{2}1text{ }|text{ }0A_{1}0text{ }|text{ }1A_{1}1 \
A_3longrightarrow 0A_{1}0text{ }|text{ }1A_{1}1text{ }|text{ }0A_{0}0text{ }|text{ }1A_{0}1 \
A_2longrightarrow 0text{ }|text{ }1text{ }|text{ }00text{ }|text{ }11 \
A_1longrightarrow epsilontext{ }|text{ }0text{ }|text{ }1 \
A_0longrightarrow epsilon
$$

And so on.

If $|y|>|z|$, then we just add the rule $$
R longrightarrow 0Rtext{ }|text{ }1Rtext{ }|text{ }0Stext{ }|text{ }1S
$$
and let $R$ be the starting symbol.

If $|y|<|z|$, then we just add the rule $$
R longrightarrow R0text{ }|text{ }R1text{ }|text{ }S0text{ }|text{ }S1
$$
and let $R$ be the starting symbol.