1.2. Проблема Туэ

Эта проблема касается повторений подслов в словах и ω-словах. Слово или ω-слово над алфавитом ∑ называется бесквадратным (бескубным), если оно не содержит подслов вида x² (соответственно x³), где x - непустое слово. Слово или ω-слово называется сильно бескубным, если оно не содержит подслов вида x²a, где x - непустое слово, а a - первая буква слова x. Очевидно, каждое бесквадратное слово или ω-слово является также сильно бескубным, и каждое сильно бескубное слово или ω-слово является бескубным.

Проблема Туэ состоит в построении бесквадратных слов максимальной возможной длины над данным алфавитом ∑, и если это возможно, то и бесквадратных ω-слов. Если это оказывается невозможным, то необходимо построить сильно бескубные слова возможно большей длины или сильно бескубные ω-слова. Проблема Туэ возникает в ряде самых разнообразных ситуаций; некоторые из них упоминаются в упр. 6-9 в конце главы. Начнем с того, что проблема Туэ упрощается (в смысле, который будет уточнен ниже) при возрастании числа букв в алфавите ∑. Образно говоря, это обеспечивает большую "свободу маневра". В частности, если ∑ состоит только из одной буквы, то над ∑ не существует бескубного слова, имеющего длину более ∑. В случае когда ∑ состоит из двух букв, только очень короткие слова могут быть бесквадратными, что видно из следующей леммы.

Лемма 1.1. Ни одно слово, имеющее длину более 3, над алфавитом ∑ из двух букв не является бесквадратным. Следовательно, над ∑ не существует бесквадратных ω-слов.

Доказательство. Пусть ∑ состоит из букв a и b. Существуют только 2 бесквадратных слова длины три:

так как все другие слова указанной длины:

содержат в качестве подслова либо a², либо b². С другой стороны, каким бы способом ни была приписана буква к любому слову из (1.4), результирующее слово в каждом случае будет содержать в качестве подслова одно из слов a², b², (ab)², (ba)² и, следовательно, не будет бесквадратным. ▫

Пусть α - слово (соответственно ω-слово) над ∑. Слово α' той же длины, что и а (соответственно ω-слово α'), называется интерпретацией слова а при выполнении следующего условия: если в слове α i'-я буква (отсчет ведется с начала) отличается от j-й буквы, то и в слове α' i-я буква отличается от j-й. Поэтому как a₁a₂a₃b₁a₄b₂, так и a₁a₂a₃a₁a₃ являются интерпретациями слова a³bab, тогда как a₁a₂a₃a₄a₅a₁ не является интерпретацией того же слова, поскольку в слове a³bab первая и последняя буквы различны. Каждая интерпретация слова или ω-слова α может быть получена (помимо возможного переименования букв) приписыванием каждой букве а из а некоторого нижнего индекса, причем можно использовать только конечное число индексов. С интерпретациями мы еще встретимся ниже (гл. 7).

Лемма 1.2. Если α (слово или ω-слово) является бесквадратным, сильно бескубным или бескубным, то любая интерпретация α' слова а будет также бесквадратной, сильно бескубной или бескубной соответственно.

Доказательство. Это утверждение непосредственно следует из определения интерпретации. Например, если α' содержит подслово вида x², то подслово, в соответствующем месте входящее в слово α, имеет вид y².▫

Лемма 1.2 показывает, что если α - бесквадратное (бескубное, сильно бескубное) ω-слово строго над ∑ (в том смысле, что все буквы из ∑ действительно входят в α), а ∑₁ - алфавит, содержащий больше букв, чем ∑, то некоторое бесквадратное (соответственно бескубное, сильно бескубное) ω-слово строго над ∑₁ может быть получено из а путем интерпретации.

Возвращаясь к проблеме Туэ, заметим, что, если мы сможем построить бесквадратное (сильно бескубное) ω-слово над ∑, мы также сможем построить произвольно длинные есквадратные (соответственно сильно бескубные) слова над ∑. (Обратная импликация не столь очевидна; однако, как мы увидим далее, она тоже верна.) Следовательно, в свете леммы 1.1 лучшие результаты, на которые можно надеяться, заключаются в решении следующих двух проблем:

(i) Построить сильно бескубное ω-слово над алфавитом из двух букв (проблема сильной бескубности).

(и) Построить бесквадратное ω-слово над алфавитом из трех букв (проблема бесквадратности).

Из леммы 1.2 следует, что, решив проблемы (i) и (и), мы сможем строить сильно бескубные (соответственно бесквадратные) ω-слова, а также слова произвольной длины, обладающие этим свойством, над любым алфавитом, состоящим не менее чем из двух (соответственно из трех) букв.

Сейчас мы приведем решения проблем (i) и (ii). Читатели, которые сами найдут решение, могут считать себя первооткрывателями (подобно Акселю Туэ) теории формальных языков.