fl_task3 (1178886)
Текст из файла
Задание 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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
