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




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

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

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

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

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

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

aba и bab, (1.4)

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

a3, a2b, ba2, b3, b2a, ab2

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

Пусть α - слово (соответственно ω-слово) над ∑. Слово α' той же длины, что и а (соответственно ω-слово α'), называется интерпретацией слова а при выполнении следующего условия: если в слове α i'-я буква (отсчет ведется с начала) отличается от j-й буквы, то и в слове α' i-я буква отличается от j-й. Поэтому как a1a2a3b1a4b2, так и a1a2a3a1a3 являются интерпретациями слова a3bab, тогда как a1a2a3a4a5a1 не является интерпретацией того же слова, поскольку в слове a3bab первая и последняя буквы различны. Каждая интерпретация слова или ω-слова α может быть получена (помимо возможного переименования букв) приписыванием каждой букве а из а некоторого нижнего индекса, причем можно использовать только конечное число индексов. С интерпретациями мы еще встретимся ниже (гл. 7).

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

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

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

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

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

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

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

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

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








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