fl_task3 (Задание 3)

Задание 3Автоматы и распознавание текстов; Лемма о накачкеКлючевые слова 1 :принцип мат. индукции, язык, регулярные выражения, конкатенация, объединение, итерация, конечные автоматы(КА), детерминированные и недетерминированные КА, регулярные языки. алгебра регулярных выражений, примеры нерегулярных языков; поиск подстрок, алгоритм Кнута- Морисса- Пратта.1НКА и ДКАИз алгоритма детерминизации НКА следует, что если НКА A имеет множество состояний QA , то построенный по нему ДКА B имеет множествомакросостояний QB ⊆ 2QA , где 2QA – множество всех подмножеств множества QA .

Таким образом, на число состояний автомата B мы имеемверхнюю оценку |QB | 6 2|QA | . То есть число состояний в ДКА ограниченно экспоненциальной функцией от числа состояний в НКА, но существует ли язык, для которого эта оценка достигается? На самом деле,когда мы говорим об оценках такого рода, нам требуется рассматриватьни один какой-то язык, а последовательность языков, по которым мы исможем установить экспоненциальную зависимость.Задача 1. Определим язык Li = {w | |w| = n, w[n−i] = 1}, то есть в языкLi входят все слова, в которых 1 стоит на i-ом месте от конца2 . ПостройтеНКА, распознающий язык L3 . По построенному НКА постройте ДКА.Задача 2∗. Докажите, что на языках Li между НКА и построеннымипо ним ДКА достигается экспоненциальный разрыв.Упражнение 1.

Почему для доказательство экспоненциального разрыва необходима бесконечная последовательность языков, а не достаточноконечной?12минимальный необходимый объём понятий и навыков по этому разделу)Во избежании путаницы, первый с конца символ – это последний символ слова.12Алгоритм Кнута-Морриса-Пратта и его связьс автоматамиНКА – очень удобный инструмент для описания автоматов, которыеищут слова в тексте. Например, автоматa, ba, bq0aq1bq2aq3bq4aq5bпроверяет имеет ли поданное на вход слово подслово ababab.Как мы уже обсуждали, для алгоритмической проверки принадлежности слова языку, распознаваемому НКА, по нему следует строить ДКА.Однако, в специальных случаях, используемых на практике, подобноописанному выше, есть более удобные алгоритмы и один из них – алгоритм Кнута-Морриса-Пратта.

Этот алгоритм подробно описан в 10ой главе книги А. Шеня «Программирование. Теоремы и задачи». Еёможно в свободном доступе скачать здесь. Я рекомендую изучить КМПалгоритм по этой книге, в этом разделе я лишь скажу пару слов о егосвязи с автоматами, а точнее дам на эту тему пару задач.В основе этого алгоритма – использование для поиска слова вычисления префикс-функции.Определение 1. Назовём префикс-функцией функцию l(), которая возвращает самый длинный несобственный3 префикс слова w, являющийсяодновременно его суффиксом.Пример 1.

Приведём пример вычисления префикс-функции.l(an+1 ) = anl(ababa) = abal(abb) = ε3То есть префикс, не совпадающий со всем словом w.2q6У префикс функции есть важное свойство – все несобственные префиксы слова w, которые являются его суффиксами лежат в последовательности l(w), l(l(w)), . . .Задача 3∗. Докажите, что в ДКА, распознающем язык Σ∗ wΣ∗ не можетбыть меньше состояний чем элементов последовательности l(w), l(l(w)), . . .На семинаре мы разобрали алгоритм построения КМП-автомата. Оносновывался на том, что КМП-автомат, который ищет в тексте t (входавтомата) слово w (фиксированный параметр автомата) имеет |w| + 1 состояние, каждое из которых кодирует некоторый префикс слова w. Еслиавтомат находится в i-ом состоянии , то это означает, что обработанныйучасток текста имеет видt1 t2 · .

. . · tk w1 w2 · . . . · wiМы считаем, что нулевое состояние кодирует пустой префикс, а значитw0 = ε. При этом, i – максимальная длина суффикса текста, совпадающая с префиксом w. Таким образом, если следующий символ текстане совпадает с символом wi+1 , то тогда необходимо найти новый максимальный по длине суффикс текста, который является префиксом wи сделать переход по отличающейся букве в состояние, соответствующееэтому префиксу. При этом, оказывается, что его длина будет обязательноменьше i.Задача 4.

Почему?Поскольку w имеет конечное число префиксов, то вычислить переходы КМП-автомата можно на конечной памяти полным перебором безовсякой науки. Но это можно сделать и используя высокую науку, обсуждение которой я был вынужден вероломно прервать на семинаре. Вкакой-то момент я сформулировал и объяснил утверждение из следующей задачи, потом часть аудитории его успела забыть, и в итоге не осталось времени с ним разбираться. Тем не менее, это утверждение верноеи позволяет ускорить вычисление переходов КМП-автомата.Задача 5∗.

Пусть l(xay) = x, где x, y слова над алфавитом {a, b}. Тогдаl(xayb) = l(xb). Докажите это утверждение.3Результаты предыдущих задач позволяют говорить о том, что КМПалгоритм можно представить в виде последовательного вычисление префиксфункции на словах видаw#t1 · . . .

· tnПри этом, вычисление l(w#t1 · . . . · tn tn+1 ) по значению l(w#t1 · . . . · tn )осуществляется за константное время, то есть ничего не стоит.Лемма о накачке43В данном разделе мы поговорим о лемме о накачке – одном из способовдоказательства нерегулярности языка.Лемма 1. Для любого регулярного языка L существует такая константа p > 1, что для любого слова w из L длиннее p, справедливо:• w = xyz• |y| > 1• |xy| 6 p• ∀i > 0, xy i z ∈ L.Доказательство. Поскольку L ∈ REG, то существует ДКА A распознающий L. Пусть A имеет N состояний. Возьмём p = N + 1. Тогда, еслиесли слово w принадлежит L и |w| > p, то это означает, что при обработке w автомат A оказался в некотором сотоянии q дважды. Пусть впервый раз автомат оказался в q после прочтения префикса x, а второйраз, при прочтении префикса xy.

Тогда δ(q, y) = q, но поскольку w = xyzпринадлежит L, то это означает, что δ(q, z) = qf ∈ F , а значит все словавида xy i z, i > 0 лежат в L.Обратите внимание, что при доказательстве леммы, я использовалте же трюки, что и в доказательстве на семинаре того, что an bn – нерегуляный язык. Также обратите внимание на то, что формула w = xyzозначает, что для слова w существует такое разбиение xyz, для котороговыполняются следующие свойства и утверждение леммы: часто студенты это равенство ошибочно воспринимают как «для любого разбиения».4Также известна как лемма о разрастании. Неудачные переводы неудачного термина «Pumping Lemma».4Пример 2.

Используем лемму о накачке для доказательства христоматийного примера нерегулярности языка L = {0n 1n | n > 0}.Доказательство. Допустим, что язык L регулярный. Тогда, по леммео накачке, существует константа p, что для любого слова w длиннее p,существует такое разбиение xyz, что |xy| 6 p и слова xy i z, i > 0 принадлежат L.Рассмотрим w = 0p 1p . Если такое разбиение существует, то y имеетвид 0k или 1k , k > 1 – в противном случае, если y = 0k 1l , то y 2 = 0k 1l 0k 1l ,но в L нет слов, в которых за 1 следует 0.

Допустим, что y = 0k . Тогдаx = 0m , z = 0l 1p , k + m + l = p. Но тогда, по лемме о накачке xy 2 z ∈ L,а значит, слово 0m+2k+l 1l ∈ L, но m + 2k + l > p, т.к. m + k + l = p иk > 0, поскольку |y| > 1. Аналогично приходим к противоречию когдаy = 1k .Упражнение 2. В предыдущем примере показано громоздкое доказательство: его можно сделать проще, убрав перебор кучи случаев, воспользовавшись структурой слова. Постарайтесь получить доказательство в одну строчку.У этой леммы слишком много минусов. Во-первых, она работает невсегда: если язык нерегулярен, это ещё не означает, что лемма о накачке для него не выполняется.

Во-вторых, она слишком громоздкая. Дажедля такого простого примера как L = {0n 1n }, неподкованному в этойнауке человеку потребуется много писанины, а в более сложных случаевперебор возможных y куда шире. Как показывает наблюдение, рукаминерегулярность доказать быстрее, да и работает техника, обсужденнаяна семинаре в тех случаях, когда применима лемма о накачке.

Но тем неменее, у этой леммы есть и плюсы – учебные. Во-первых, лемма о накачкепоказывает структуру регулярного языка: разность длин двух последовательных слов из регулярного языка ограниченна линейной функцией.Во-вторых, сущетсвует ещё лемма о накачке для КС-языков, для понимания которой стоит изучить более простую лемму о накачке для регулярных языков. В случае КС-языков, доказательство непринадлежностиязыка классу КС уже куда менее очевидно, так что лемма о накачке становится мощным и одним из основных инструментов.Задача 6. Применить лемму о накачке для доказательства нерегулярnности языка L = {a2 | n > 0}.54Дополнительные задачиЗадача 7.

Приведите протокол работы КМП-алгоритма при поискеподслова abba в слове abbbababbab.6.