Seja L o conjunto de expressôes em que só ocorrem os símbolos ( e ), assim definidas:
  • () é uma expressão;
  • se alpha é uma expressão, então ( alpha ) é uma expressão;
  • se alpha e beta são expressões, então alpha beta é uma expressão.
    onde alpha beta 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.

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:
  1. número de “(” em α = número de “)” em α;
  2. em qualquer prefixo de α, fechados ≤ abertos.
    Faremos base e depois os dois casos de construção de L.

Passo 3

Base: α = “()”.
  1. Conta de parênteses: há um “(” e um “)”, logo iguais.
  2. 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.
  1. 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(α).
  2. 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.
  1. Conta total: abertos(α)=abertos(β)+abertos(γ), fechados(α)=fechados(β)+fechados(γ). Por P(β) e P(γ), esses somatórios são iguais, logo abertos(α)=fechados(α).
  2. 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.

Exercícios relacionados