Defina de forma recorrente a linguagem no alfabeto
composta por todas as cadeias contendo o mesmo número de símbolos
e
. Prove que toda string na sua definição possui a mesma quantidade de símbolos
e
.
Passo 1
Beleza, vamos entender o que a questão está pedindo. Temos um alfabeto
e queremos definir de forma recorrente uma linguagem composta por todas as cadeias que têm o mesmo número de símbolos
e
. Além disso, precisamos provar que qualquer cadeia nessa linguagem realmente possui a mesma quantidade de
e
. 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 , tem 0 símbolos
e 0 símbolos
, então claramente tem o mesmo número de ambos.
A cadeia vazia, representada por
Regras de Produção:
Para construir cadeias com a mesma quantidade de e
, podemos adicionar pares de símbolos que equilibram a contagem. Por exemplo:
Para construir cadeias com a mesma quantidade de
- Se
é uma cadeia na linguagem, então também está na linguagem. - Se
é uma cadeia na linguagem, então também está na linguagem. - Se
e são cadeias na linguagem, então sua concatenação 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
e
. Para isso, usaremos o princípio da indução matemática.
Base da Indução:
A cadeia vazia tem 0
e 0
, então a propriedade é verdadeira.
A cadeia vazia
Passo Indutivo:
Assumimos que para uma cadeia na linguagem, o número de
é igual ao número de
. Agora, vamos mostrar que adicionar
no início e
no final (
) mantém essa igualdade:
Assumimos que para uma cadeia
-
tem e . -
tem e .
O mesmo vale para a regra
:
-
tem e . -
tem e .
Para a concatenação
, onde ambas
e
têm igual número de
e
:
- Se
tem e , e tem e , então tem e .
Resposta
Assim, por indução, qualquer cadeia definida recursivamente na linguagem possui o mesmo número de símbolos
e
.