Quais destes códigos são códigos de prefixo?
a) a:
b) a:
c) a:
d) a: 010 , e:
a) a:
b) a:
c) a:
d) a: 010 , e:
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
e
, não acontece que
seja prefixo inicial de
.
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 .
Todas têm comprimento . Como não há palavras mais curtas, nenhuma pode ser prefixo de outra.
Conclusão: a) é código de prefixo.
As palavras são
Todas têm comprimento
Conclusão: a) é código de prefixo.
Passo 4
Opção b)
As palavras são ,
com comprimentos .
Repare que a palavra (comprimento
) aparece no início de
e de
.
Conclusão: b) não é código de prefixo.
As palavras são
com comprimentos
Repare que a palavra
Conclusão: b) não é código de prefixo.
Passo 5
Opção c)
As palavras são ,
com comprimentos .
A mais curta é (comprimento
), e nenhum dos outros começa por
. Não há nenhuma outra relação de prefixo.
Conclusão: c) é código de prefixo.
As palavras são
com comprimentos
A mais curta é
Conclusão: c) é código de prefixo.
Passo 6
Opção d)
As palavras são ,
com comprimentos .
A mais curta é ; nenhum dos demais começa por
. Em seguida, palavras de comprimento
não aparecem ao início de outra, e o mesmo vale para as de comprimento
e
.
Conclusão: d) é código de prefixo.
As palavras são
com comprimentos
A mais curta é
Conclusão: d) é código de prefixo.
Resposta
a), c) e d) são códigos de prefixo.