Considere
como o conjunto de cadeias definidas recursivamente por
e
, em que
e
são letras fixas; e para todo
e
, em que
é uma variável que representa uma cadeia de letras.
a) Encontre todos os elementos de
de extensão oito ou menos.
b) Mostre que todo elemento de
tem uma extensão divisível por três.
a) Encontre todos os elementos de
b) Mostre que todo elemento de
Passo 1
O enunciado define o conjunto
de cadeias sobre as letras
por dois fatos:
- Base: as cadeias “abc”, “bac” e “acb” pertencem a
. - Fechamento: se
, então inserindo o bloco “abc” em quatro posições fixas – antes de , logo após “a”, logo após “ab” ou após – o resultado continua em .
O que precisamos:
- Em (a) listar todas as cadeias em
de comprimento até . - Em (b) mostrar que todo
tem comprimento múltiplo de .
Passo 2
Observe que as cadeias de
têm sempre comprimento da forma
pois a base tem comprimento
e cada operação de inserção acrescenta exatamente
letras. Logo, as únicas extensões
possíveis são
e
.
Passo 3
As cadeias de extensão
são exatamente as da base:
abc, bac e acb.
abc, bac e acb.
Passo 4
Para obter extensão
, basta aplicar uma das quatro operações a cada cadeia de extensão
. Faremos isso para cada base:
- Para
abc:
- abcx = abcabc
- abxc = ababcc
- axbc = aabcbc
- xabc = abcabc (repetida)
- Para
bac:
- abcx = abcbac
- abxc = abbacc
- axbc = abacbc
- xabc = bacabc
- Para
acb:
- abcx = abcacb
- abxc = abacbc (já apareceu)
- axbc = aacbbc
- xabc = acbabc
Passo 5
Reunindo e eliminando repetições, as cadeias de extensão
em
são:
abcabc, ababcc, aabcbc, abcbac, abbacc, abacbc, bacabc, abcacb, aacbbc e acbabc.
abcabc, ababcc, aabcbc, abcbac, abbacc, abacbc, bacabc, abcacb, aacbbc e acbabc.
Passo 6
Prova de que toda cadeia em
tem extensão múltipla de
:
- Base: as cadeias iniciais têm extensão
. - Passo indutivo: se
tem extensão múltiplo de , inserir o bloco “abc” acrescenta exatamente letras, mantendo o total múltiplo de .
Portanto, por indução, todo elemento detem extensão divisível por .
Resposta
a) As cadeias em
de extensão até
são:
extensão 3: abc, bac, acb
extensão 6: abcabc, ababcc, aabcbc, abcbac, abbacc, abacbc, bacabc, abcacb, aacbbc, acbabc
extensão 6: abcabc, ababcc, aabcbc, abcbac, abbacc, abacbc, bacabc, abcacb, aacbbc, acbabc
b) Como a base tem extensão
e cada passo adiciona exatamente
letras, por indução toda cadeia em
tem extensão múltipla de
.