Изменения
Нет описания правки
Рассмотрим язык <tex>G = \{0, 1\}^t</tex> для некоторого <tex>t</tex>. Определим операцию <tex>\oplus</tex> над словами из этого языка как побитовое исключающее или.
Назовем <tex>X</tex>, содержащееся в <tex>G</tex>, <tex>k</tex>-большим, если существует такой набор <tex>\{g_i\}_{i=1}^{k} \subset G</tex>, что <tex>\bigcup\limits_{i=1}^{k} g_i \oplus X = GU</tex>. Иначе будем называть <tex>X</tex> — <tex>k</tex>-маленьким.
Если <tex>|X| < \frac{2^t}{k}</tex>, то <tex>X</tex> является <tex>k</tex>-маленьким (так как <tex>k</tex> копий <tex>X</tex> не смогут покрыть <tex>G</tex>). Найдем достаточное условие, при котором <tex>X</tex> является <tex>k</tex>-большим.
