= Solution
A <context-free grammar> is a quadruple $(N,\Sigma,P,S)$: $N$ is a finite <set> of nonterminal symbols, $\Sigma$ is a disjoint finite <alphabet> of terminal symbols, $S\in N$ is the start symbol, and $P$ is a finite <set> of productions $A\to\alpha$, with $A\in N$ and $\alpha\in(N\cup\Sigma)^*$. Its <formal language> consists of the terminal <strings> derivable from $S$.
For the even-length <palindromes> in (b)(ii), take terminal <alphabet> $\{0,1\}$ and the <context-free grammar>
$$
\boxed{S\to0S0\mid1S1\mid\varepsilon.}
$$
Every production adds identical symbols at the two ends, so every generated <string> is an even-length <palindrome>. Conversely, remove the matching outer pair of any nonempty even-length <palindrome> and repeat; this constructs its derivation, ending with $\varepsilon$.
For the unequal-block <formal language> in (b)(iv), use
$$
\boxed{\begin{aligned}
S&\to A\mid B,\\
A&\to0A1\mid Z,& Z&\to0Z\mid0,\\
B&\to0B1\mid O,& O&\to1O\mid1.
\end{aligned}}
$$
After $k$ uses of $A\to0A1$, and $j\geq1$ zeros from $Z$, the resulting <string> is $0^{k+j}1^k$, so its zero count is larger. Every such unequal pair with $m>n$ occurs by choosing $k=n,j=m-n$. Similarly $B$ generates exactly $0^k1^{k+j}$ with $j\geq1$, covering precisely $m<n$. The start alternatives cover both possibilities and never equal counts. If positive exponents are required, replace the start productions by $S\to0A1\mid0B1$, which adds one matched pair and ensures both counts are positive.
Back to article page
