Show that the language $L=\{w|w$ has odd length and the middle symbol is a $0\}$ is Context-Free and construct a PDA that accepts it

Question

Were w is any string composed over the alphabet $\Sigma = \{0,1\}$.

1. For the first part of the exercise I've tried decomposing the problem into three different ones, mainly the first one is for the string before the 0 the second one for the 0 itself and the third for the rest of the string after the 0. This is what I came up with: $$ \begin{align} S &\rightarrow S_{1}S_{2}S_{3} \\ S_{1} &\rightarrow 0S_{1}|1S_{1}|\varepsilon \\ S_{2} &\rightarrow 0 \\ S_{3} &\rightarrow 0S_{3}|1S_{3}|\varepsilon \end{align} $$

But I'm not sure if the presence of the $\epsilon$ means that input strings such as $01$ or $10$ could be accepted, or if the $\epsilon$ at the end just ensure the recursion of the grammar.

2. For the second part I have no idea about a possible solution.

Any help would be most appreciated. Thanks in advance

Answer 1

In your solution there is no guarantee that the words generated by $S_1$ and $S_2$ will have the same length. The trick is to generate both sides simultaneously: $$S \to 0S0 \mid0S1 \mid1S0 \mid1S1 \mid 0.$$

As for the second part, there are mechanical procedures to convert a CFG into a PDA.