Considere S como o conjunto de cadeias definidas recursivamente por a b c \in S, b a c \in S e a c b \in S, em que a, b e c são letras fixas; e para todo x \in S, a b c x \in S ; a b x c \in S, a x b c \in S e x a b c \in S, em que x é uma variável que representa uma cadeia de letras.
a) Encontre todos os elementos de S de extensão oito ou menos.
b) Mostre que todo elemento de S tem uma extensão divisível por três.

Passo 1

O enunciado define o conjunto S de cadeias sobre as letras a,b,c por dois fatos:
  1. Base: as cadeias “abc”, “bac” e “acb” pertencem a S.
  2. Fechamento: se x\in S, então inserindo o bloco “abc” em quatro posições fixas – antes de x, logo após “a”, logo após “ab” ou após x – o resultado continua em S.
O que precisamos:
  • Em (a) listar todas as cadeias em S de comprimento até \,8.
  • Em (b) mostrar que todo x\in S tem comprimento múltiplo de 3.

Passo 2

Observe que as cadeias de S têm sempre comprimento da forma
3 + 3n,
pois a base tem comprimento 3 e cada operação de inserção acrescenta exatamente 3 letras. Logo, as únicas extensões \le 8 possíveis são 3 e 6.

Passo 3

As cadeias de extensão \,3 são exatamente as da base:
abc, bac e acb.

Passo 4

Para obter extensão \,6, basta aplicar uma das quatro operações a cada cadeia de extensão 3. Faremos isso para cada base:
  1. Para x= abc:
  • abcx = abcabc
  • abxc = ababcc
  • axbc = aabcbc
  • xabc = abcabc (repetida)
  1. Para x= bac:
  • abcx = abcbac
  • abxc = abbacc
  • axbc = abacbc
  • xabc = bacabc
  1. Para x= acb:
  • abcx = abcacb
  • abxc = abacbc (já apareceu)
  • axbc = aacbbc
  • xabc = acbabc

Passo 5

Reunindo e eliminando repetições, as cadeias de extensão 6 em S são:
abcabc, ababcc, aabcbc, abcbac, abbacc, abacbc, bacabc, abcacb, aacbbc e acbabc.

Passo 6

Prova de que toda cadeia em S tem extensão múltipla de 3:
  • Base: as cadeias iniciais têm extensão 3.
  • Passo indutivo: se x\in S tem extensão múltiplo de 3, inserir o bloco “abc” acrescenta exatamente 3 letras, mantendo o total múltiplo de 3.
    Portanto, por indução, todo elemento de S tem extensão divisível por 3.

Resposta

a) As cadeias em S de extensão até 8 são:
extensão 3: abc, bac, acb
extensão 6: abcabc, ababcc, aabcbc, abcbac, abbacc, abacbc, bacabc, abcacb, aacbbc, acbabc
b) Como a base tem extensão 3 e cada passo adiciona exatamente 3 letras, por indução toda cadeia em S tem extensão múltipla de 3.

Exercícios de Livros Relacionados