Defina de forma recorrente a linguagem no alfabeto Sigma=a, b composta por todas as cadeias contendo o mesmo número de símbolos a e b. Prove que toda string na sua definição possui a mesma quantidade de símbolos a e b.

Passo 1

Beleza, vamos entender o que a questão está pedindo. Temos um alfabeto Sigma = a, b e queremos definir de forma recorrente uma linguagem composta por todas as cadeias que têm o mesmo número de símbolos a e b. Além disso, precisamos provar que qualquer cadeia nessa linguagem realmente possui a mesma quantidade de a e b. Para resolver isso, vamos precisar entender como definir linguagens de forma recorrente e usar indução para a prova.

Passo 2

Primeiro, vamos definir a linguagem de forma recorrente. Uma definição recorrente tem duas partes principais: casos base e regras de produção (ou regras de construção).
Caso Base:
A cadeia vazia, representada por epsilon, tem 0 símbolos a e 0 símbolos b, então claramente tem o mesmo número de ambos.
Regras de Produção:
Para construir cadeias com a mesma quantidade de a e b, podemos adicionar pares de símbolos que equilibram a contagem. Por exemplo:
  1. Se omega é uma cadeia na linguagem, então a omega b também está na linguagem.
  2. Se omega é uma cadeia na linguagem, então b omega a também está na linguagem.
  3. Se omega1 e omega2 são cadeias na linguagem, então sua concatenação omega1 omega2 também está na linguagem.

Passo 3

Agora que temos a definição recorrente, vamos provar que toda cadeia construída dessa forma tem o mesmo número de a e b. Para isso, usaremos o princípio da indução matemática.
Base da Indução:
A cadeia vazia epsilon tem 0 a e 0 b, então a propriedade é verdadeira.
Passo Indutivo:
Assumimos que para uma cadeia omega na linguagem, o número de a é igual ao número de b. Agora, vamos mostrar que adicionar a no início e b no final ( a omega b) mantém essa igualdade:
  • omega tem n a e n b.
  • a omega b tem n + 1 a e n + 1 b.
O mesmo vale para a regra b omega a:
  • omega tem n a e n b.
  • b omega a tem n + 1 a e n + 1 b.
Para a concatenação omega1 omega2, onde ambas omega1 e omega2 têm igual número de a e b:
  • Se omega1 tem n a e n b, e omega2 tem m a e m b, então omega1 omega2 tem n + m a e n + m b.

Resposta

Assim, por indução, qualquer cadeia definida recursivamente na linguagem possui o mesmo número de símbolos a e b.

Exercícios relacionados