О СЛОВАХ, ИЗБЕГАЮЩИХ КВАДРАТОВ С ОДНОЙ ВОЗМОЖНОЙ ОШИБКОЙ ЗАМЕЩЕНИЯ

Статья посвящена некоторым вопросам, связанным с существованием периодических структур в словах из формальных языков. Рассматриваются квадраты, т.е. фрагменты вида хх, где х — произвольное слово, и квадраты с одной ошибкой — фрагменты вида ху, где слово х отличается от слова у на одну букву. Устанавливается существование сколь угодно длинных слов, не содержащих квадратов с длиной больше lо и квадратов с одной ошибкой и длиной больше l1 в зависимости от натуральных чисел lо и l1. Для всех возможных пар li > lо найден минимальный алфавит, над которым можно построить такое слово.

• Котляров Н.В.

• Прикладные науки. Медицина. Технология

• Физико-математические науки