T04 Expressões bem formadas
Considere o alfabeto \(\Sigma=\{({\,,\,}){\,,\,}z\}\) (o alfabeto $\Sigma$ tem três elementos: os parênteses e $z$). Seja $\Sigma^*$ o conjunto de todas as palavras (isto é, cadeias de caracteres) que podemos formar com as letras (isto é, elementos) de $\Sigma$. Definimos o conjunto $B\subset\Sigma^*$ das palavras bem formadas ou expressões bem formadas sobre $\Sigma$ da seguinte forma recursiva:
(1) $z\in B$ e
(2) se $s\in B$ e $t\in B$, então $(st)\in B$.
Mais formalmente, $B$ é definido como o menor subconjunto de $\Sigma^*$ que satisfaz (1) e (2).
Seja $b(N)$ o número de palavras bem formadas sobre $\Sigma$ com $N$ pares de parênteses. Assim, $b(0)=1$, $b(1)=1$, $b(2)=2$ e $b(3)=5$. Por exemplo, $b(2)=2$ devido às expressões bem formadas $(z(zz))$ e $((zz)z)$ e o fato que não há outras expressões bem formadas com dois pares de parênteses (isto é algo que podemos verificar por inspeção).
(i) Liste todas as expressões bem formadas com $1$ par de parênteses.
(ii) Liste todas as expressões bem formadas com $3$ pares de parênteses.
(iii) Determine $b(4)$.
(iv) Determine uma recorrência para $b(N)$ para todo $N\geq1$, explicando por que ela é válida. Sua recorrência para $b(N)$ pode envolver $b(0),b(1),\dots$ e $b(N-1)$.