dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 33
Текст из файла (страница 33)
4.1.2. Ïðèìåíåíèå ëåììû î íàêà÷êåРассмотрим несколько примеров использования леммы о накачке. В каждом примере эталемма применяется для доказательства нерегулярности некоторого предлагаемого языка.Ëåììà î íàêà÷êå êàê èãðà äâóõ ïðîòèâíèêîâВ разделе 1.2.3 говорилось о том, что любую теорему, утверждение которой содержитнесколько чередующихся кванторов “для всех” (“для любого”) и “существует”, можнопредставить в виде игры двух противников.
Лемма о накачке служит важным примеромтеорем такого типа, так как содержит четыре разных квантора: “для любого регулярного языка L существует n, при котором для всех w из L, удовлетворяющих неравенству|w| ≥ n, существует цепочка xyz, равная w, удовлетворяющая …”. Применение леммы онакачке можно представить в виде игры со следующими правилами.4.1. ÄÎÊÀÇÀÒÅËÜÑÒÂÎ ÍÅÐÅÃÓËßÐÍÎÑÒÈ ßÇÛÊÎÂСтр. 1451451.
Игрок 1 выбирает язык L, нерегулярность которого нужно доказать.2. Игрок 2 выбирает n, но не открывает его игроку 1; первый игрок должен построить игру для всех возможных значений n.3. Игрок 1 выбирает цепочку w, которая может зависеть от n, причем ее длина должна быть не меньше n.4. Игрок 2 разбивает цепочку w на x, y и z, соблюдая условия леммы о накачке, т.е.y ≠ ε и |xy| ≤ n. Опять-таки, он не обязан говорить первому игроку, чему равны x, yи z, хотя они должны удовлетворять условиям леммы.5. Первый игрок “выигрывает”, если выбирает k, которое может быть функцией от n,x, y и z и для которого цепочка xykz не принадлежит L.Пример 4.2.
Покажем, что язык Leq, состоящий из всех цепочек с одинаковым числомнулей и единиц (расположенных в произвольном порядке), нерегулярен. В терминах игры, описанной во врезке “Лемма о накачке как игра двух противников”, мы являемся игроком 1 и должны иметь дело с любыми допустимыми ходами игрока 2. Предположим,что n — это та константа, которая согласно лемме о накачке должна существовать, еслиязык Leq регулярен, т.е. “игрок 2” выбирает n. Мы выбираем цепочку w = 0n1n, котораянаверняка принадлежит Leq.Теперь “игрок 2” разбивает цепочку w на xyz. Нам известно лишь, что y ≠ ε и |xy| ≤ n.Но эта информация очень полезна, и мы “выигрываем” следующим образом. Поскольку|xy| ≤ n, и цепочка xy расположена в начале цепочки w, то она состоит только из нулей.Если язык Leq регулярен, то по лемме о накачке цепочка xz принадлежит Leq (при k = 0 влемме)2.
Цепочка xz содержит n единиц, так как все единицы цепочки w попадают в z. Нов xz нулей меньше n, так как потеряны все нули из y. Поскольку y ≠ ε, то вместе x и z содержат не более n – 1 нулей. Таким образом, предположив, что язык Leq регулярен, приходим к ошибочному выводу, что цепочка xz принадлежит Leq. Следовательно, методомот противного доказано, что язык Leq нерегулярен. Пример 4.3. Докажем нерегулярность языка Lpr, образованного всеми цепочками изединиц, длины которых — простые числа. Предположим, что язык Lpr регулярен.
Тогдадолжна существовать константа n, удовлетворяющая условиям леммы о накачке. Рассмотрим некоторое простое число p ≥ n + 2. Такое p должно существовать, посколькумножество простых чисел бесконечно. Пусть w = 1p.Согласно лемме о накачке можно разбить цепочку w = xyz так, что y ≠ ε и |xy| ≤ n.Пусть |y| = m. Тогда |xz| = p – m. Рассмотрим цепочку xyp–mz, которая по лемме о накачкедолжна принадлежать языку Lpr, если он действительно регулярен. Однако|xyp–mz| = |xz| + (p – m)|y| = p – m + (p – m)m = (m + 1)(p – m).2146Стр. 146Заметим, что можно выиграть и при k = 2 или любом другом значении k, кроме k = 1.ÃËÀÂÀ 4.
ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂПохоже, что число |xyp–mz| не простое, так как имеет два множителя m + 1 и p – m. Однако нужно еще убедиться, что ни один из этих множителей не равен 1, потому что тогдачисло (m + 1)(p – m) будет простым. Из неравенства y ≠ ε следует m ≥ 1 и m + 1 > 1. Кроме того, m = |y| ≤ |xy| ≤ n, а p ≥ n + 2, поэтому p – m ≥ 2.Мы начали с предположения, что предлагаемый язык регулярен, и пришли к противоречию, доказав, что существует некоторая цепочка, которая не принадлежит этомуязыку, тогда как по лемме о накачке она должна ему принадлежать.
Таким образом, языкLpr нерегулярен. 4.1.3. Óïðàæíåíèÿ ê ðàçäåëó 4.14.1.1.Докажите нерегулярность следующих языков:а) {0n1n | n ≥ 1}. Это язык L01, который рассматривался в начале раздела. Емупринадлежат все цепочки, состоящие из нулей, за которыми следует такое жеколичество единиц. Здесь для доказательства примените лемму о накачке;б) множество цепочек, состоящих из “сбалансированных” скобок “(” и “)”, которые встречаются в правильно построенном арифметическом выражении;в) (∗) {0n10n | n ≥ 1};г) {0n1m2n | n и m — произвольные целые числа};д) {0n1m | n ≤ m};е) {0n12n | n ≥ 1}.4.1.2.(!) Докажите нерегулярность следующих языков:а) (∗) {0n | n — полный квадрат};б) {0n | n — полный куб};в) {0n | n — степень числа 2};г) множество цепочек из нулей и единиц, длины которых — полные квадраты;д) множество цепочек из нулей и единиц вида ww, где некоторая цепочка w повторяется дважды;е) множество цепочек из нулей и единиц вида wwR, где за цепочкой следует цепочка, обратная к ней (формальное определение цепочки, обратной к данной,см.
в разделе 4.2.2);ж) множество цепочек из нулей и единиц вида w w , где цепочка w образованаиз w путем замены всех нулей единицами и наоборот. Например, 011 = 100,так что цепочка 011100 принадлежит данному языку;з) множество цепочек из нулей и единиц вида w1n, где w — цепочка из нулей иединиц длиной n.4.1. ÄÎÊÀÇÀÒÅËÜÑÒÂÎ ÍÅÐÅÃÓËßÐÍÎÑÒÈ ßÇÛÊÎÂСтр. 1471474.1.3.(!!) Докажите нерегулярность следующих языков:а) множество всех цепочек из нулей и единиц, которые начинаются с единицыи удовлетворяют следующему условию: если интерпретировать такую цепочку как целое число, то это число простое;3б) множество цепочек вида 0i1j, для которых наибольший общий делитель чисел i и j равен 1.4.1.4.(!) При попытке применения леммы о накачке к регулярным языкам “противниквыигрывает”, и закончить доказательство не удается.
Определите, что именнопроисходит не так, как нужно, если в качестве L выбрать следующий язык:а) (∗) пустое множество;б) (∗) {00, 11};в) (∗) (00 + 11)*;г) 01*0*1.4.2. Ñâîéñòâà çàìêíóòîñòè ðåãóëÿðíûõ ÿçûêîâВ этом разделе доказано несколько теорем вида “если определенные языки регулярны, а язык L построен из них с помощью определенных операций (например, L есть объединение двух регулярных языков), то язык L также регулярен”. Эти теоремы часто называют свойствами замкнутости регулярных языков, так как в них утверждается, чтокласс регулярных языков замкнут относительно определенных операций.
Свойства замкнутости выражают идею того, что если один или несколько языков регулярны, то языки,определенным образом связанные с ним (с ними), также регулярны. Кроме того, данныесвойства служат интересной иллюстрацией того, как эквивалентные представления регулярных языков (автоматы и регулярные выражения) подкрепляют друг друга в нашемпонимании этого класса языков, так как часто один способ представления намного лучше других подходит для доказательства некоторого свойства замкнутости.Основные свойства замкнутости регулярных языков выражаются в том, что эти языкизамкнуты относительно следующих операций.1.Объединение.2.Пересечение.3.Дополнение.4.Разность.5.Обращение.3148Стр.
148Иными словами, это двоичные записи простых чисел. — Прим. ред.ÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂ6.Итерация (звездочка).7.Конкатенация.8.Гомоморфизм (подстановка цепочек вместо символов языка).9.Обратный гомоморфизм.4.2.1. Çàìêíóòîñòü ðåãóëÿðíûõ ÿçûêîâ îòíîñèòåëüíîáóëåâûõ îïåðàöèéСначала рассмотрим замкнутость для трех булевых операций: объединение, пересечение и дополнение.1.Пусть L и M — языки в алфавите Σ. Тогда язык L U M содержит все цепочки, которые принадлежат хотя бы одному из языков L или M.2.Пусть L и M — языки в алфавите Σ. Тогда язык L I M содержит все цепочки, принадлежащие обоим языкам L и M.3.Пусть L — некоторый язык в алфавите Σ. Тогда язык L , дополнение L, — это множество тех цепочек в алфавите Σ*, которые не принадлежат L.×òî äåëàòü, åñëè ÿçûêè èìåþò ðàçíûå àëôàâèòû?При объединении или пересечении двух языков L и M может оказаться, что они определены в разных алфавитах.
Например, возможен случай, когда L1 ⊆ {a, b}, а L2 ⊆{b, c, d}. Однако, если язык L состоит из цепочек символов алфавита Σ, то L можнотакже рассматривать как язык в любом конечном алфавите, включающем Σ(надмножестве Σ). Например, можно представить указанные выше языки L1 и L2 какязыки в алфавите {a, b, c, d}.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
