Defina de forma recorrente a linguagem no alfabeto
composta por todas as cadeias contendo um número par de símbolos
. Prove que toda cadeia na sua definição possui uma quantidade par de símbolos
.
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.