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

Passo 1

O enunciado pede para definir recursivamente a linguagem L sobre Σ={a,b} que contém todas as cadeias com número par de símbolos a e, em seguida, provar que toda cadeia gerada tem de fato um número par de a’s. Vamos usar teoria de linguagens formais (definições recursivas) e prova por indução estrutural.

Passo 2

Proponho a seguinte definição recursiva de L: • Base: ε ∈ L (a cadeia vazia tem zero a’s, que é par). • Recorrência: se w ∈ L então: 1) b w ∈ L e w b ∈ L (adiciona b sem alterar o número de a’s); 2) a w a ∈ L (adiciona dois a’s, preservando a paridade).

Passo 3

Para provar que toda cadeia em L tem número par de a’s, façamos indução estrutural sobre as derivações em L.

Passo 4

Base da indução: ε ∈ L e ε tem zero símbolos a. Como zero é par, a propriedade vale.

Passo 5

Passo indutivo: suponha que, para uma cadeia arbitrária w ∈ L derivada em menor profundidade, w tem número par de a’s. Vamos analisar cada caso de construção recursiva: • Caso b w (ou w b): o número de a’s em b w é igual ao número de a’s em w (pois b não contribui com a’s). Por hipótese indutiva, w tem número par de a’s, logo b w também tem número par de a’s. Mesma argumentação vale para w b. • Caso a w a: o número de a’s em a w a é o número de a’s em w mais 2 (as duas extremidades). Por hipótese w tem número par de a’s, e somar 2 a um número par resulta em número par. Portanto a w a tem número par de a’s.

Passo 6

Assim, por indução estrutural, toda cadeia em L definida recursivamente tem número par de símbolos a.

Resposta

Definição recursiva de L sobre Σ={a,b}:
Base: ε ∈ L
Recorrência: se w ∈ L então:
• b w ∈ L
• w b ∈ L
• a w a ∈ L
Prova (síntese): ε tem 0 a’s (par). Se w tem número par de a’s, então b w e w b mantêm esse número, e a w a acrescenta 2 a’s, preservando a paridade. Logo, toda cadeia em L tem número par de símbolos a.

Exercícios relacionados