Seja L o conjunto de expressôes em que só ocorrem os símbolos ( e ), assim definidas:
- () é uma expressão;
- se
é uma expressão, então (
) é uma expressão;
- se
e
são expressões, então
é uma expressão.
onde
denota a justaposição das duas expressões. Mostre que em qualquer expressão de L:
(a) o número de parêntesis abertos é igual ao número de parêntesis fechados.
(b) em qualquer prefixo duma expressão, o número de parêntesis fechados não excede o número de parêntesis abertos.
onde
(a) o número de parêntesis abertos é igual ao número de parêntesis fechados.
(b) em qualquer prefixo duma expressão, o número de parêntesis fechados não excede o número de parêntesis abertos.
Passo 1
A questão define L como o conjunto de expressões bem-parentisadas geradas a partir de:
- Base: “()” é expressão;
- Se α é expressão, então “(α)” é expressão;
- Se α e β são expressões, então a justaposição αβ é expressão.
Precisamos mostrar duas propriedades para toda α∈L:
(a) o número de parênteses abertos iguala o de fechados;
(b) em qualquer prefixo de α, o número de fechados não ultrapassa o de abertos.
Passo 2
Vamos provar ambas as propriedades simultaneamente usando indução estrutural em α. Definimos a propriedade P(α) como a conjunção de:
- número de “(” em α = número de “)” em α;
- em qualquer prefixo de α, fechados ≤ abertos.
Faremos base e depois os dois casos de construção de L.
Passo 3
Base: α = “()”.
- Conta de parênteses: há um “(” e um “)”, logo iguais.
- Prefixos de “()” são:
– ε (vazio): abertos=0, fechados=0 → fechados≤abertos;
– “(”: abertos=1, fechados=0 → fechados≤abertos;
– “()”: abertos=1, fechados=1 → fechados≤abertos.
Logo P("()") vale.
Passo 4
Caso 1: α = (β), onde β∈L e P(β) vale por hipótese de indução.
- Conta total: α tem um “(” extra no início e um “)” no fim, então
abertos(α)=1+abertos(β), fechados(α)=fechados(β)+1. Como abertos(β)=fechados(β), segue abertos(α)=fechados(α). - Prefixos de α:
– Prefixo só “(”: abertos=1, fechados=0 → OK.
– Prefixo “(”+u, onde u é prefixo próprio de β: abertos=1+abertos(u), fechados=fechados(u). Por hipótese fechados(u)≤abertos(u), logo fechados≤abertos.
– Prefixo completo α: já vimos abertos=fechados.
Logo P((β)) vale.
Passo 5
Caso 2: α = βγ, com β,γ ∈ L e P(β),P(γ) verdadeiras.
- Conta total: abertos(α)=abertos(β)+abertos(γ), fechados(α)=fechados(β)+fechados(γ). Por P(β) e P(γ), esses somatórios são iguais, logo abertos(α)=fechados(α).
- Prefixos de α são de dois tipos:
a) prefixo u de β: por P(β), fechados(u)≤abertos(u);
b) prefixo que é β concatenado com u’, onde u’ é prefixo de γ. Então
fechados(βu’)=fechados(β)+fechados(u’),
abertos(βu’)=abertos(β)+abertos(u’).
Mas fechados(β)=abertos(β) e, por P(γ), fechados(u’)≤abertos(u’). Soma dá fechados(βu’)≤abertos(βu’).
Logo P(βγ) vale.
Passo 6
Pelas etapas de indução estrutural (base e casos de construção), P(α) vale para toda expressão α∈L, o que demonstra as propriedades (a) e (b).
Resposta
As propriedades (a) e (b) são válidas para qualquer expressão em L, conforme demonstrado por indução estrutural.