I'm just looking to understand if my justification I wrote makes sense (it might not) in a) b).
Note: I'm doing exercises from a textbook which has no solutions I can see. So I can't check my answer or understand what I am doing if wrong.
Question:
Give context-free grammars that generate the following languages over $\{0,1\}$:
(a) $\{w \; : \; w \text{ starts and ends with the same symbol}\}$
(b) $\{w \; : \; \text{the length of } w \text{ is odd}\}$
a)
$S_0 \rightarrow 0S_10 \; | \; 1S_11 \; | \; \varepsilon$
$S_1 \rightarrow 0S_1 \; | \; 1S_1 \; | \; \varepsilon$
Justification:
$S_0$ must start with $0$ and end with $0$ OR start with $1$ and end with $1$ OR can be empty.
$S_1$ must start with $0$ OR start with $1$ OR can be empty.
b)
$S_0 \rightarrow 0S_1 \; | \; 1S_1$
$S_1 \rightarrow 00S_1 \; | \; 01S_1 \; | \; 10S_1 \; | \; 11S_1 \; | \; \varepsilon$
Justification:
$S_0$ must start with $0$ OR $1$ (which is odd).
$S_1$ must start with $00$ OR $01$ OR $10$ OR $11$ OR empty.
What I don't understand:
Why is $S_1$ in $S_0$ but $S_0$ is not in $S_1$?
What do $S_0$ and $S_1$ represent?
(I think $S_0$ is string with binary string $0$ and $S_1$ is string with binary string $1$?
$S_1$ and $S_0$ are variables. A context-free grammar has at least one variable, and one of these variables is designated as the start variable, which is the variable that every derivation of a string must begin with. Let's say that we always denote the start variable by $S$.
So for your question a), we could as well write
$S \rightarrow 0B0 \; | \; 1B1 \; | \; \varepsilon$
$B \rightarrow 0B \; | \; 1B \; | \; \varepsilon$
To understand why the variable names are not important, take a look at the following derivation: $$S \Rightarrow 0B0 \Rightarrow 00B0 \Rightarrow 001B0 \Rightarrow 001\varepsilon 0 \Rightarrow 0010$$ Notice that at the end, all of the variables have disappeared from the string anyway, so the exact names of the variables are not important. Other than that, both your answers look correct.