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




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

1.4. Решение проблемы бесквадратности

Теперь обратимся к проблеме построения бесквадратного ω-слова над алфавитом из трех букв. Фактически мы можем вывести основное утверждение из уже доказанной теоремы 1.5. Это оказывается возможным благодаря применению одного полезного и весьма распространенного в теории формальных языков приема, состоящего в группировке нескольких букв в одну. С помощью этого приема прежде всего докажем следующую лемму.

Лемма 1.6. Существует бесквадратное ω-слово β над алфавитом из четырех символов.

Доказательство. Рассмотрим ω-слово α из теоремы 1.5. Определим новый алфавит ∑1 следующим образом;

1 = {[aa], [ab], [ba], [bb]}.

Используя выражение (1.7) для α, определим над алфавитом ∑1 ω-слово

β = d1d2d3 ....(1.14)

полагая

d1 = [cjcj+1] для всех j≥1.

Предположим, что y2 входит в качестве подслова в β, т. е.

y = dj+1 ... dj+t = dj+t+1 ... dj+2t, t≥1.

Следовательно,

[cj+1cj+2]...[ci+tcj+t+1] = [cj+t+1cj+t+2]...[cj+2tcj+2t+1].

Это означает, что cj+1 = cj+t+1 = cj+2t+1 и cj+n = cj+t+n для 1≤n≤t. Значит, (cj+1 ... cj+t)2cj+1 входит в качестве подслова в α, что противоречит теореме 1.5. Следовательно, β бесквадратно. ▫

Усилим лемму 1.6 до желаемого результата. Для этого удобно ввести новые обозначения для элементов ∑1, положив

[aa] = 1, [ab] = 2, [ba] = 3, [bb] = 4.

Теперь начало β примет вид

2432312431232432312324312432312 ...

(сравните с (1.6)). По определению β перед символом 1 должен стоять символ 1 или 3. Однако если перед символом 1 стоит он же, то a3 входит в качестве подслова в α, что невозможно в силу леммы 1.3. Значит, в β перед символом 1 всегда стоит символ 3. Точно так же выводятся остальные утверждения следующей леммы.

Лемма 1.7. В β символу 1 всегда предшествует символ 3, а за символом 1 всегда следует символ 2. Символу 4 всегда предшествует символ 2, а за символом 4 всегда следует символ 3.

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

Теорема 1.8. Существует бесквадратное ω-слово γ над алфавитом из трех символов.

Доказательство. Рассмотрим алфавит ∑2 = {1,2,3}. Определим ω-слово у как результат замены в β всех вхождений символа 4 символом 1. Таким образом, начало γ будет иметь вид

γ = 2132312131232132312321312132312 ... .

Покажем, что γ является бесквадратным.

Предположим противное: пусть xx входит в качестве подслова в γ, причем x непусто. Отсюда следует, что β содержит подслово y1y2, такое, что |y1| = |y2| = |x| = t, и, кроме того, y1 и y2 совпадут, если заменить в них все вхождения символа 4 символом 1.

Прежде всего заметим, что t≥2, так как в силу леммы 1.7 ни одно из слов 11, 14, 41, 44 не входит в качестве подслова в β.

Пусть в обозначениях (1.14)

y1 = dj+1...dj+t, y2 = dj+t+1...dj+2t.

Тогда для любого n, удовлетворяющего неравенствам 1≤n≤t, имеем dj+n = dj+n+t, за исключением случая, когда один из символов dj+n и dj+n+t есть 1, а другой 4. Мы докажем, что этот исключительный случай в действительности невозможен.

Рассмотрим сначала фиксированное значение n, удовлетворяющее неравенствам 1≤n<t. Если dj+n есть 1 (соответственно 4), то в силу леммы 1.7 dj+n+1 есть 2 (соответственно 3). Следовательно, по нашему допущению относительно y1 и y2, dj+n+1+t тоже есть 2 (соответственно 3). Далее, еще раз применив лемму 1.7, получим

dj+n = dj+n+t, 1≤n<t.(1.15)

Обратимся теперь к символам dj+t и dj+2t и в нашем доказательстве, основанном на лемме 1.7, вместо последующих символов будем рассматривать предыдущие. Если dj+t есть 1 (соответственно 4), то dj+t-1 есть 3 (соответственно 2). Значит, dj+t = dj+2t. Из последнего равенства и (1.15) следует, что (dj+1 ... dj+t)2 входит в качестве о том, что xx входит в γ в качестве подслова, неверно, и тем самым теорема 1.8 доказана.▫

Подведем итог полному решению проблемы Туэ в следующей теореме.

Теорема 1.9. Если ∑ состоит не менее чем из трех символов, то над ∑ существует бесквадратное ω-слово. Если ∑ состоит из двух символов, то над ∑ существует сильно бескубное ω-слово, но не существует бесквадратных слов, имеющих длину более 3.

Мы хотим подчеркнуть, что в формулировке предыдущей теоремы выражение "существует" фактически означает, что искомое ω-слово может быть эффективно построено: используя (1.5), мы можем вычислить любой символ в α, β, γ. За немногими исключениями,и другие доказательства теории формальных языков дают метод построения искомых объектов.

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








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