НОВОСТИ   БИБЛИОТЕКА   ЮМОР   КАРТА САЙТА   ССЫЛКИ   О САЙТЕ  




предыдущая главасодержаниеследующая глава

1.3. Решение проблемы сильной бескубности

Рассмотрим DOL-систему G =({a, b}, h, a), где морфизм h определяется следующим образом: h(a) = ab, h(b) = ba. Тогда последовательность S(G) начинается словами

a, ab, abba, abba baab, abba baab baab abba, ....

Вообще, для всех i≥1 (i+1)-е слово wi+1 последовательности S(G) удовлетворяет равенству

wi+1 = wiwi'.

где через x' обозначается слово, которое получается из слова x заменой всех a и b и наоборот.

Докажем равенство (1.5) по индукции. При i=1 оно очевидно. Переход от i к i+1 выглядит так:

wi+2 = h (wi+1) = h(wiwi') = h (wi) h(wi') = wi+1h(w'i) = wi+1w'i+1.

где последнее равенство выполняется, так как h(x') = (h(x))' для всех x по определению h.

Пусть теперь α есть ω-слово, порожденное DOL-системой G. Мы хотим доказать, что а является сильно бескубным. Заметим, что равенство (1.5) дает удобный способ написания произвольно длинного начала ω-слова α. Используя группировку, представленную в (1.5) получаем сверхслово

a b ba baab baababba baababbaabbabaab ...(1.6)

Таким образом, (1.6) - это некоторое начало ω-слова α. Пробелы использованы только для того, чтобы было ясно, где приписывается новое wi'.

Для доказательства основной теоремы нам понадобятся некоторые свойства ω-слова α. Будет полезно записывать α также в виде

α = c1c2c3 ...,(1.7)

где каждое cj - либо a, либо b.

Лемма 1.3. Ни a3, ни b3 не входят в качестве подслова в α. Ни ababa, ни babab не входят в качестве подслова в α. Следовательно, любое подслово x ω-слова α, такое, что |x| = 5, содержит в качестве подслова либо a2, либо b2.

Доказательство. Докажем первое утверждение. Если слово a3 или b3 входит в качестве подслова в α, то оно входит в качестве подслова в некоторое wi. Но это невозможно, так как wi = h(wi-1) и, следовательно, wi получено приписыванием слов ab и ba в некотором порядке.

Докажем второе утверждение. Предположим, что ababa входит в качестве подслова в ω-слово α, начиная с j-й его буквы. Тогда, используя обозначения (1.7), запишем

cjcj+1cj+2cj+3cj+4 = ababa.(1.8)

Выберем настолько большое i, что |wi|≥j+4. Тогда вхождение (1.8) целиком лежит в wi. Еще раз используя соотношение wi = h(wi-1), заключаем, что в wi-1 в качестве подслова входит либо a3, либо b3 в зависимости от того, является ли j в (1.8) нечетным или четным. Но это невозможно в силу доказанного выше первого утверждения леммы. Таким же способом (или воспользовавшись соображениями симметрии) можно убедиться в том, что babab не входит в α.

Наконец, последнее утверждение является следствием второго, так как, за исключением слов ababa и babab, любое слово длины 5 над {a, b} содержит в качестве подслова a2 или b2.▫

Лемма 1.4. Предположим, что a2 или b2 входит в качестве подслова в α, начиная с j-й буквы; тогда j четно.

Доказательство. Используя обозначения (1.7), предположим, что cjcj+1 есть a2 или b2. Вновь выбираем такое i, что |wi|≥j+1, и применяем соотношение wi = h(wi-1). В силу этого соотношения, если j нечетно, то cjcj+1 есть либо h(a), либо h(b). Так как ни h(a), ни h(b) не есть a2 или b2, лемма доказана.▫

Теперь мы можем доказать основную теорему.

Теорема 1.5. ω-слово а является сильно бескубным.

Доказательство. Вновь рассуждая от противного, предположим, что xxc, где c - первая буква x, есть подслово слова а и что никакое слово yyd, где d - первая буква y и |y|<|x|, не является полсловом слова α. (Иначе говоря, ххс - кратчайший возможный контрпример к теореме 1.5.) Если |x| = 1 или |x| = 2, то одно из слов a3, b3, ababa, babab входит в качестве подслова в α. Так как в силу леммы 1.3 это невозможно, заключаем, что

|x| = t ≥ 3.(1.9)

Предположим, что рассматриваемое вхождение xxc начинается с j-й буквы α. Тогда в обозначениях (1.7) имеем

cj ... cj+2t = xxc.(1.10)

По лемме 1.3 и (1.9) или a2, или b2 входит в качестве подслова в xx. Из этого следует, что или a2, или b2дважды входит в качестве подслова в xxc. Действительно, a2 или b2 должно входить в качестве подслова или в x, или в xc. В обоих случаях оно дважды входит в xxc. Теперь из леммы 1.4 можно вывести, что |x|=t является четным числом. Действительно, если бы t было нечетным, то хотя бы одно из вхождений a2 или b2 в xxc должно было бы начинаться с k-й буквы α при некотором нечетном k. Но это невозможно в силу леммы 1.4.

Следовательно, t = 2u для некоторого натурального числа u. Предположим сначала, что j в (1.10) четно и, следовательно, j≥2. Применяя наш обычный прием, т. е. выбирая достаточно большое число i (такое, что |wi|≥j+2t) и используя соотношение wi = h(wi-1), получаем, что

cj-1cj = ab или cj-1cj = ba.(1.11)

Поскольку j+t четно, отсюда следует, что

cj-1+tcj+t = ab или cj-1+tcj+1 = ba.(1.12)

Согласно (1.10) cj = cj+t. Из последнего равенства и равенств (1.11), (1.12) вытекает, что cj-1 = cj-1+t. Следовательно,

cn = cn+t, где j-1≤n≤j+i.(1.13)

Для 0≤n≤1 слово cj-1+2ncj+2n есть либо h(a), либо h(b). Это следует из соотношения wi = h(wi-1) и нечетности числа j-1.

Теперь в силу (1.13) заключаем, что wi-1 содержит подслово yyd, где d - первая буква слова y и |y| = t/2 = u. Следовательно, α содержит yyd в качестве подслова. Но это противоречит выбору x. Нам осталось рассмотреть случай, когда j в (1.10) до буквы cj+2t+1 вместо cj-1. Так как числа j+t и j+2t нечетны, слова cj+tcj+t+1 и cj+2tcj+2t+1 имеют вид либо h(a), либо h(b), как это было в (1.11) и (1.12). Следовательно, из равенства cj+t = cj+2t вытекает равенство cj+t+1 = cj+2t+1. Значит,

cn = cn+t, где j≤n≤j+t+1.

Так же как и в предыдущем случае, отсюда следует, что α содержит подслово yyd, где d - первая буква слова y и |y| = u, что снова противоречит выбору x. Мы показали, что α является сильно бескубным ω-словом над алфавитом {a, b}, и тем самым завершили доказательство теоремы 1.5.▫

предыдущая главасодержаниеследующая глава








© Злыгостев А.С., 2001-2019
При использовании материалов сайта активная ссылка обязательна:
http://informaticslib.ru/ 'Библиотека по информатике'
Рейтинг@Mail.ru