Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Топ:
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Интересное:
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Дисциплины:
2020-10-20 | 157 |
5.00
из
|
Заказать работу |
|
|
Аксель Туэ (1863 – 1922) – норвежский математик. Хотя он был специалистом по теории чисел, но остался в истории, как родоначальник теории формальных языков, связанные с решёнными им задачами о формальных словах известных теперь, как проблемы Туэ. Задачи решены в 1912 – 1914г.
I. Введём следующие определения.
1) Сформулируем определение - слова:
Бесконечная последовательность элементов алфавита А называется - словом или сверхсловом. Таким образом, - слово может быть отождествлено с отображением множества целых чисел в А. Очень удобным средством задания конкретных - слов являются DOL – системы.
2) Тройка G = (A, h, w), A – алфавит, - морфизм и w – слово над А, называется DOL – системой. DOL – система G определяет S(G) слов над А:
.
Рассмотрим DOL – систему G = (A, h, w), такую, что , х Z(A), т.е. w – собственное начало слова h(w) и, кроме того, h является нестирающим (т.е. h(a)= для всех а из А). Тогда
и вообще
для всех i 0.
Последнее равенство показывает, что для всех i является собственным началом слова . Следовательно, - слово может быть определено как “ предел ” последовательности , i=0,1,2, …. Точнее, представляет собой - слово, начало которого, имеющее длину , есть , i=0,1,2, ….
3) Определение. Слово или - слово называется бесквадратным (бескубным), если оно не содержит подслова вида хх (соответственно х ), где х – непустое слово.
Слово или - слово называется сильно бескубным, если если оно не содержит слов вида хх а, где х – непустое слово, а а – первая буква слова х.
4) Может случиться, что слово w содержит два “перекрывающихся” вхождения х, т.е. подслово xy = zx, где . Если это не имеет место, то будем называть w словом без перекрытий.
|
II. Сформулируем основные теоремы.
Рассмотрим следующую DOL – систему G = ({a, b}, h, a), где h определяется следующим образом: h(a) =ab, h(b) = ba. Тогда последовательность S(G) начинается словами:
a, ab, abba, abba baab, abba baab baab abba, ….
Теперь есть - слово, порожденное DOL – системой G.
- слово является сильно бескубным.
Сформулируем следующее:
Существует бесквадратное - слово над алфавитом из четырех символов и cуществует бесквадратное - слово над алфавитом из трёх символов .
= где для всех j 1.
Введём новые обозначения для элементов А1, положив
[aa] = 1, [ab] = 2, [ba] = 3, [bb] = 4.
Теперь начало имеет вид
2432312431232432312324312432312…
Рассмотрим алфавит А2 = {1, 2, 3}. Определим - слово кА результат замены в всех вхождений символа 4 символом 1.
Теперь подведём итог полному решению проблемы Туэ в следующих теоремах:
1) “Если А состоит не менее чем из трёх символов, то над А существует бесквадратное - слово ”;
2) “Если А имеем не менее двух символов, то А существует сильно бескубное, а значит и бескубное - слово”.
III.Сейчас рассмотрим некоторые методы доказательства.
В формулировках основных теорем показано, как строятся - слова .
Теорема 3.1.
Слово и - слово свободно от перекрытий тогда и только тогда, когда оно является сильно бескубным.
Доказательство. Пусть w не свободно от перекрытий. Тогда w найдется подслово xy = zx, такое, что имеет место . Пусть а – первая буква слова z. По нашему предположению, x = zx , где первой буквой слова x также будет а. Следовательно, zza – подслово w и w не является сильно бескубеым.
Наоборот, предположим, что w не является сильно бескубным. Тогда в w найдётся слово z z a, где а – первая буква z . Пологая z =аz мы видим, что х = а z а, y = z а, z = а z . Тогда xy = zx – подслово w, и, кроме того, выполняется . Отсюда следует, что w не свободно от перекрытий. Ч.т.д.
Теорема 3.2.
|
Ни одно слово, имеющее длину более 3, над алфавитом А из двух букв не является бесквадратным. Следовательно, над алфавиотм А не существует бесквадратных - слов.
Доказательство. Пусть А состоит из букв a и b. Существуют только 2 бесквадратных слова
аbа и bаb, (*)
так как все другие слова указанной длины:
содержит в качестве подслова либо , либо . С другой стороны, каким бы способом ни была приписана буква к любому слову из (*), результирующее слово в каждом случае будет содержать в качестве подслова одно из слов , , и, следовательно, не будет бесквадратным.Ч.т.д.
Теоремя 3.3.
Ни , ни не входят в качестве подслова в . Ни ababa, ни babab не входят в качестве подслова в . Следовательно, любое подслово х - слова , такое, что , содержит в качестве подслова либо , либо .
Доказательство. Докажем первое утверждение. Если слово или входит в качестве подслова в , то оно входит в качестве подслова в некоторое w . Но это не возможно, так как w = h(w ) и, следовательно, w получено приписыванием слов ab и ba в некотором порядке.
Докажем второе утверждение. Предположим, что ababa входит в качестве подслова в - слова , начиная с j-й его буквы. Тогда используя = …, запишем
= ababa. (**)
Выберем настолько большое j что . Тогда вхождения (**) целиком лежит в w .Ещё раз используя соотношение w = h(w ), заключаем, что в w в качестве подслова входит либо , либо в зависимости от того, является ли j в (**) нечетным или четным. Но это не возможно в силу доказанного выше первого утверждения. Аналогично и для babab не входит в .
Наконец, последнее утверждение является следствием второго, так как, за исключением слов ababa и babab, любое слово длины 5 над {a,b} содержит в качестве подслова либо , либо . Ч.т.д.
Теорема 3.4.
Предположим, что или входит в качестве подслова в , начиная с j-й; тогда j четно.
Доказательство. Используя обозначения предыдущей теоремы, предположим, что есть или . Вновь выбираем такое i, что , и применяем соотношение w = h(w ). В силу этого соотношения, если j нечетно, то есть либо h(a), либо h(b). Так как ни h(a), ни h(b) не есть или .Ч.т.д.
Литература
1. Курош А.Т. Лекции по общей алгебре. – М.: Наука, 1973.
|
2. Лаллеман Ж. Полугруппы и комбинаторные приложения. – М.: Мир, 1985.
3. Саломаа А. Жемчужины теории формальных языков. – М.: Мир, 1986.
4. Скорняков Л.А. Элементы алгебры. – М.: Наука, 1986.
|
|
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!