Construct a CFG for $L = \{ w \in \{0,1\}^*\text{ } |\text{ } w = w^R \text{ and } |w| \text{ is even}\}$ I need to construct a CFG for the following language$$L = \{ w \in \{0,1\}^*\text{ } |\text{ } w = w^R \text{ and } |w| \text{ is even}\}$$
I know that the two middle position should always be the same. E.g. $11,00,0\underline{11}0,0\underline{00}0,\dots$ Each position on the opposite sides of the middle points should also be the same.
So these are the production rules of the CFG I came up with
$$
S\rightarrow00$$
$$S\rightarrow11$$
$$S\rightarrow ASA$$
$$A\rightarrow1$$
$$A\rightarrow0$$
$$A\rightarrow \epsilon$$
Is this solution correct?
As HendrikJan stated, we can for example obtain the following languages with above CFG
$$01, 0001,\dots$$
which do not meet the required conditions.
Instead, we need to make sure that the ends are always the same. We can do that by the following production rules.
$$
S\rightarrow 0S0$$
$$S\rightarrow 1S1$$
$$S\rightarrow \epsilon$$