4. По каналу связи передаются сообщения, содержащие только заглавные латинские буквы. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: A – 111, B – 000, C – 01, D – 1101, E – 100, F – 0010. Укажите кратчайшее возможное кодовое слово для буквы G. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Условие Фано требует, чтобы ни одно кодовое слово не было началом другого.

1. Код длины 1 невозможен: 0 является началом кода B = 000, а 1 — началом кодов A, D и E.
2. Коды длины 2 также невозможны: 00 конфликтует с B, 01 совпадает с C, 10 является началом E, а 11 — началом A и D.
3. Из кодов длины 3 коды 000, 001, 010, 011, 100, 110 и 111 конфликтуют с известными кодами. Код 101 не является началом и не имеет началом ни одного из них.

Ответ: 101.