2015-05-20
1817
Определение. Префиксом слова 
называется любая последовательность 
, где 
. Префикс называется собственным, если 
.
Определение. Суффиксом слова называется любая последовательность 
, где 
, суффикс называется собственным, если 
.
Рассмотрим 
– множество собственных префиксов и собственных суффиксов кодовых слов, которые сами не являются кодовыми словами. Если 
, тогда существуют кодовые слова 
и 
и непустые слова 
и 
, принадлежащие ɱ 
, такие что 
и 
.
Кодированию 
сопоставим ориентированный граф 
, где 
, 
– пустое слово (слово без букв), 
– множество собственных префиксов и собственных суффиксов кодовых слов. Пара 
тогда и только тогда, когда существуют кодовые слова 
, такие что 
– кодовое слово. При этом на 
накладываются следующие ограничения:
1) если 
и 
, тогда 
;
2) если 
или 
, тогда 
;
3) если 
, тогда 
.
