Quais destes códigos são códigos de prefixo?
a) a: 11, e: 00, t: 10, s: 01
b) a: 0, e: 1, t: 01, s: 001
c) a: 101, e: 11, t: 001, s: 011, n: 010
d) a: 010 , e: 11, t: 011, s: 1011, n: 1001, i: 10101

Passo 1

O enunciado dá quatro atribuições de palavras binárias para símbolos e pergunta quais delas são códigos de prefixo. O que vamos usar é a definição de código de prefixo:
Um conjunto de palavras binárias é um código de prefixo se, para quaisquer duas palavras distintas x e y, não acontece que x seja prefixo inicial de y.

Passo 2

Para cada opção, primeiro anotamos os comprimentos das palavras e depois vemos se alguma palavra mais curta aparece ao início de outra mais longa.

Passo 3

Opção a)
As palavras são \{\,11,\,00,\,10,\,01\}.
Todas têm comprimento 2. Como não há palavras mais curtas, nenhuma pode ser prefixo de outra.
Conclusão: a) é código de prefixo.

Passo 4

Opção b)
As palavras são \{\text{0},\,\text{1},\,\text{01},\,\text{001}\},
com comprimentos 1,1,2,3.
Repare que a palavra \text{0} (comprimento 1) aparece no início de \text{01} e de \text{001}.
Conclusão: b) não é código de prefixo.

Passo 5

Opção c)
As palavras são \{\text{101},\,\text{11},\,\text{001},\,\text{011},\,\text{010}\},
com comprimentos 3,2,3,3,3.
A mais curta é \text{11} (comprimento 2), e nenhum dos outros começa por \text{11}. Não há nenhuma outra relação de prefixo.
Conclusão: c) é código de prefixo.

Passo 6

Opção d)
As palavras são \{\text{010},\,\text{11},\,\text{011},\,\text{1011},\,\text{1001},\,\text{10101}\},
com comprimentos 3,2,3,4,4,5.
A mais curta é \text{11}; nenhum dos demais começa por \text{11}. Em seguida, palavras de comprimento 3 \text{010},\text{011} não aparecem ao início de outra, e o mesmo vale para as de comprimento 4 e 5.
Conclusão: d) é código de prefixo.

Resposta

a), c) e d) são códigos de prefixo.

Exercícios de Livros Relacionados