В.Б. Алексеев - Введение в теорию сложности алгоритмов (1114530), страница 9
Текст из файла (страница 9)
Пусть М распознает симметрию, а1аз и 616з — симметричные слова и бм(а1 ~а2) = ~м(61 ~6з). Тогда а16з — симметричное слово. Доказательство. Так как М распознает симметрию, то при ра.- боте на словах а1аз и ЬА она остановится в состоянии 4~ ("да"), а при работе на слове а16г она также обязательно остановится в некотором состоянии.
Но тогда из леммы 4.1 следует, что и при работе на слове азиз она остановится в состоянии д' ("да"). Так как М распознает симметрию, то это означает, что азЬз — симметричное слово. Лемма доказана. Онредепение. Пусть а = аьаз и пусть (а1! = 1 (1а! — данна слова а). Тогда через см(а) будем обозначать см(а1~аг). Пусть (~ = (дз, 4з,..., д„) — множество всех состояний мыпины М. Пусть 1 < з ( н и С Е 1г'* (б — слово в алфавите Я). Через А" (з, С) будем обозначать множество всех симметричных двоичных слов а длины н, таких, что с (а) =б.
Лемма 4.4. Для любого1, такого, что 1 < ь < Д), и для любого С Е ьГ' выполняется неравенство: )Ап(з ~)( ( 2ГЫ ' Доказательство. Пусть а Е А"(ъ,с), Ь Е А"(з,б), а = а1аз, Ь = ЬзЬз и )а1 / = /Ь1! = 1. Тогда слова а и Ь симметричны и см(а~!аг) = ~м(Ь|(Ьз). По лемме 4.3 отсюда следует, что слово а1Ьз тоже симметрично. Поскольку оба алова а1Ьз и Ь|Ьз симметричны и (а1 ! = (Ь1! < 1г/, то а1 = Ьь Следовательно, у всех слов из А" (ь', с) одинаковое начало длины 1.
Поскольку симметричные слова однозначно определяются своими первыми (аз1 буквами, то ~А (, г)~ < 2ЫЬ1-' Лемма 4.5. Пусть Я = 1ды оз,...,д,) — алфавит, в комаром т > 2. Тогда количество различных слов длины не более д в алфавите Я не превосходитп т"'+). Доказатпельстпво. Число таких слов равно г + гз+ ге+ ° ° + т" = — < т' т»+т -» Л+1 Г-1 Определение. Пусть с = сопят > О. Через А„",(т) будем обозначать множество всех симметричных двоичных слов а длины и, таких, что длина следа )Стм(а)~ < (сп).
Лемма 4.6. Если машина М имеет г состпояний, тпо для ихтбоео т', тпакого, чтпо 1 < т < (Ц, вьтполняептся неравенстпво: Доказатпельстпво. Из лемм 4.4 и 4.5 додучаем )А»(т)/ < ~~~ /А"(т с)/ < 2) ) ' ° т'" < 2) " '+»»витт «к)<)с») Определение. Пусть с = сопят > О. Через В," будем обозначать множество всех симметричных двоичных слов а длины п, татсвх, что )ф(а)~ < (сп) хотя бы дпя одного т такого, что Д) < т' < Я). Лемма 4.7. )В»~ < („+8)2»)т~»вз,т) Доказатпельстпво.
Согласно лемме 4.6 для ввтбого т, такого, что 14) < т ~< 1з), выполняется неравенство: 1А»( )( < ~)»)-)»)+ы!ок,~ Поэтому )В,"( < (- — (-) + 1)2) ) )т)" )»Я" < < (и+2)2»+~3»Я,~»з ( +8)2»Я+»)»Я»~) 4 Лемма 4.8. Сушестпвуетп констпантпа см > О, тпакая, чтпо !В,"„~ »-ню 2)т) Доказатпельстпво. Согпасно лемме 4.7, ) В") с < (и+ 8)2») —,'+»3овтт) 2)г) Поэтому утверждение леммы 4.8 будет выполняться для любой константы с < 2~~-;.
Продолжим доказательство теоремы Барздиня. Выберем для данной машвны М константу см, удовлетворякллую условию леммы 4.8. Пусть 13," — множество всех симметричных двоичных слов, не входящих в В,". По леммам 4.2 и 4.8 имеем Ф." ! Вш 4м и-но 2)11 поэтому почти все симметричные двоичные слова входят в Ю,"„. При этом для любого а Е В", и любого з, такого, что (4) (~ 1 ~ (Д), вьшолняетсянеравенство См(а) > (са).
Так как время работы машины Тьюрннга не меныпе, чем длина всех следов, то для всех слов а Е В," имеем: см(а) > (~-) — (-))(смл) > — и 2 4 8 при достаточно больших л. Теорема 4.6 доказана. 4.4. Регулярные языки Регулярные языки — это языки, распознаваемые автоматами. В этом контексте автомат можно алределнть как машину Тьюринга со следующими ограничениями: головка машины на каждом шаге движется вправо или машина останавливаетсл; машина останавливается тогда и только тогда, когда головка обозревает символ й; машина останавливается в одном из двух состояний д' ("принять") или д" ("отвергнуть" ).
Определение. Пусть С вЂ” ленточный алфавит автомата М и А = С~(й). Пусть | С А'. Будем говорить, что автомат М расаозваетл язык Ь, если для любого слова а б А' работа М при входном слове а (в стандартной начальной конфвгурапни) заканчиваегся состоянием ч, если а Е Ь, и заканчивается состоянием д", если а ф Ъ. Определение. Пусть А — некоторый алфавит н Ь С А'— некоторый язык в алфавите А. Для каждого слова а е А' остпатпочный язык Ьа определим следующим образом э Е Ьа ~==~ аэ Е Ь.
Язык называется регуаярнмм, если у него лишь конечное число различных остаточных языыы. (Злесь рассматривается н 6 = Л вЂ” пустое слово; при этом й Е Ьэ Ф=~ а Е Ь). В теории автоматов и языков доказывается следующая теорема [см., например, [111). Теорема 4.7. 1) Язык, распознаваемый любым автоматом, регулярен. Й) Пля любого регулэрного языка существует распознающий его автомат. Спедствие. Если язык Ь регулярен, то для него существует распознающая его машина Тьюринга, время работы которой (число шагов) на каждом входном слове длины и равно н+ 1.
Оказывается, что не существует языков, дпя распознавания которых на машинах Тьюринга достаточно времени существенно меньшего, чем ть1ойэ и [и — длина вхапного слова) и не достаточно времени п + 1. Более точно зто выражается в приводимых виже теоремах. Теорема 4.8. Пусть машина Тьюринга М распознает язык Ь С А' и пусть существует кнстанта с ) 0 такая, что при работе М на любом входном слове а й А' длина следа с. [а) (см. стр. ВВ) не превосходит с для всех 1 < 1 < п, где и — длина слова а. Тогда Š— регулярный язык. (Следовательно, существует автомат, распознающий Ь с с = 1).
Показательство. Пусть а е А*. Построим множество .Рв всех следов, которые могут получиться при работе М на словах вида ах б А' в точке з, раздепяюшей а и х. Пусть спец дадндн... дц й .Ра. Рассмотрим работу машины М слева от разделяющей точки. Она одноэначно определяется словом а и теми состояниями д„, дц,..., в которых находится машина, когда головка возврашается на левую зону через точку й По условию э < с. Если в четно, то мапшна остававпивается слева от точки й В этом случае к последовательности дц д;,дц припишем +, если М останавливается в состоянии "принять", и припишем —, ески М останавливается в состоянии "отвергнуть".
Так как э < с, то возможных следов конечное число и разных возможных множеств Рв также конечное число. Тогда утверждение теоремы 4.8 вытекает из следующей леммы. Лемма 4.9. Если Рь = Рь, то остаточные языка Ьг и Ьу совпадают. Показательство. Пусть х — любое слово из А'. Рассмотрим работу М на словах ах и 6х. Пусть дцдцдц... д„и да дв... дз — следы в точках, раздепяюшнх а и х, 8 и й. Заметим, что работа справа от Разпапяющих точек однозначно определяется словом х н состояниями дцдцдц... и дйд;,дй..., в которых головка переходит через раздепяюшие точки вправо. При этом дц и дй однозначно опредепяются по а и 6. Так как Рв = Р1, то д;, = дй и работа справа после первого перехода через разделяющие точки происходит одинаково.
Тогда д;, = дтт. Опять, так как Р, = РЬ, то дт, = д, и опять работа справа происходит одинаково. Последовательно получаем, что з = т и дь = д., дпя всех т = 1, 2,..., и. Если з нечетно, то после перехода вправо в состоянии д,, в обоих случаях работа справа будет одинаковой и, следовательно, М остановится в одном и том же состоянии.
Если з четно, то машина в обоих случаях остановится слева от разделяющей точки, причем в одном и том же состоянии, поскольку Р, = РЬ и саед дтч д;,... д;, в обоих множествах дополнен одним и тем же знаком + ипи —. Таким образом, М принимает алово ах тогда и только тогда, когда она принимает слово Ьх, то есть либо оба слова входят в Ь, либо оба не входят в Ь.
Поэтому Ье — — Ц. Этим доказана лемма, а вместе с ней и теорема 4.5. Покажем теперь несколько лемм, которые используем в следующей теореме. Лемма 4.10. Пустпь А = 1аьам...,а,) — алфавитп, ЬьЬз,...,Ь„ — разные слова в этом олфаеите, 1т — длина с юва 6; и 1„= пьэх;!, Тогда 1„> с!окзп, где с > Π— некоторая констпантпа, зависятцая только от т. Локозательстпво.
Лемма очевидно выполняется при т = 1. Пусть т > 2. Все п слов имеют длину, не превосходящую 1„, Но всего таких слов не больше, чем т' +' (см. лемму 4.5). Поэтому п ( т' +', 1„,, > !оя, п — 1 > ст !оя, п = те-„- !ояз п. Лемма доказана. Лемма 4.11. При условиях леммы сутцестпвуетп констпанта с > О тиакая, чтпо 2," 1; > сп !окг п. Показательситво. Лемма очевидно выполняется при т = 1.
Пусть т' > 2. Число всех слов длины меньшей, чем !1!ое п! не превосходит -'1о ь ь!о ь т!г~~~""! ( тт ~~е " = „тп. Поэтому среди слов 6, не менее, чем п — чти слов, имеют длину не меньше чем !з !оя„п~. Поэтому 1 1, > !и — чтп)!-!оя,п'! > сп!оязи 2 1=1 для некоторой константы с. Лемма 4.12. Пусть числовая последоватпельносить пыля,...,тц,... не ограничена сверху. Тогда из нее можно выделитпь иодиоследоватпельность тн„тц„... такую, что для любого з и всех 1 < т < т, выполняется ~ < тц,. Показательство. Первым элементом подпоспедоватепьности возьмем пь Пусть уже выбраны и„, и;„..., п;,.
Тогда, просматривая элементы по порядку после пт„в качестве очередного элемента выбираем шрвый элемент и но больший, чем тц,. Поскольку тц,, > п,„а все элементы между пи н тц,, не превосходят и;„, то все они меньше, чем пт т,. Поэтому, если все элементы и исходной последовательности с ) = 1,2,...,т, — 1 меньше, чем пт„то все элементы пу с ) = 1,2,...,т,.„т — 1 меньше, чем пт,.г Таким образом по индукпии проверяется требуемое свойство. То, что и;„, существует, следует из неограниченности исходной последовательности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
