Свойства регулярных языков (1134638), страница 6
Текст из файла (страница 6)
Эти производные применяются к регулярнымжение a\L записывается какdaвыражениям аналогично тому, как обычные производные применяются к арифметическим выражениям. Таким образом, если R — регулярное выражение, тоdRdLобозначает то же, что и, если L = L(R):dadad ( R + S ) dR dS=+;а) докажите, чтоdada daб) (∗!) напишите правило для “производной” от RS. Указание. Нужно рассмотреть два случая: язык L(R) включает или не включает цепочку ε. Это правило4.2. ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂ1634.2.6.не совпадает с “правилом произведения” для обычных производных, но похоже на него;d ( R*);в) (!) найдите “производную” от итерации, т.е.daг) используя формулы (а)–(в), найдите производную регулярного выражения(0 + 1)*011;dL=∅;д) (∗) опишите такие языки L, для которыхd0dLе) (∗!) опишите такие языки L, для которых= L.d0(!) Докажите замкнутость регулярных языков относительно следующих операций:а) min(L) = {w | w принадлежит L, но ни один собственный префикс цепочки wне принадлежит L};б) max(L) = {w | w принадлежит L, но для любого x ≠ ε цепочка wx не принадлежит L};в) init(L) = {w | для некоторого x цепочка wx принадлежит L}.Указание.
Как и в упражнении 4.2.2, проще всего начать с ДКА для L и преобразовать его для получения нужного языка.4.2.7.(!) Если w = a1a2…an и x = b1b2…bn — цепочки одинаковой длины, то определимalt(w, x) как цепочку, в которой символы цепочек w и x чередуются, начиная с w,т.е. a1b1a2b2…anbn. Если L и M — языки, определим alt(L, M) как множество цепочек вида alt(w, x), где w — произвольная цепочка из L, а x — любая цепочкаиз M такой же длины. Докажите, что из регулярности языков L и M следует регулярность языка alt(L, M).4.2.8.(∗!!) Пусть L — язык. Определим half(L) как множество первых половин цепочекязыка L, т.е. множество {w | существует x, для которой wx принадлежит L, причем|x| = |w|}.
Например, если L = {ε, 0010, 011, 010110}, то half(L) = {ε, 00, 010}. Заметим, что цепочки с нечетной длиной не влияют на half(L). Докажите, что еслиязык L регулярен, то half(L) также регулярен.4.2.9.(!!) Упражнение 4.2.8 можно распространить на многие функции, определяющиедлину части цепочки. Если f — функция, определенная на множестве целых чисел, то обозначим через f(L) множество цепочек {w | существует цепочка x, длякоторой |x| = f(|w|) и wx принадлежит L}.
Например, операция half соответствуеттождественной функции f(n) = n, так как для цепочек из языка half(L) выполняется |x| = |w|. Покажите, что если язык L регулярен, то язык f(L) также регулярен,где f — одна из следующих функций:а) f(n) = 2n (т.е. используются первые трети цепочек);164ÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂб) f(n) = n2 (длина выбираемой части цепочки равна квадратному корню длиныоставшейся части цепочки);в) f(n) = 2n (длина выбираемой части цепочки равна логарифму длины ее остатка).4.2.10. (!!) Пусть L — язык, не обязательно регулярный, в алфавите {0}, т.е. цепочкиязыка L состоят из одних нулей.
Докажите, что язык L* регулярен. Указание. Напервый взгляд эта теорема кажется абсурдной. Чтобы проиллюстрировать истинность утверждения теоремы, приведем один небольшой пример. Рассмотримязык L = {0i | i — простое число}, который, как известно, нерегулярен (см. пример 4.3). Нетрудно доказать, что если j ≥ 2, то 0j принадлежит L*. Посколькучисла 2 и 3 — простые, цепочки 00 и 000 принадлежат L. Если j — четное число,то 0j можно получить, повторив j/2 раз цепочку 00, а если j — нечетное, можновзять одну цепочку 000 и (j – 3)/2 цепочек 00. Следовательно, L* = ε + 000*.4.2.11. (!!) Докажите замкнутость регулярных языков относительно следующей операции: cycle(L) = {w | цепочку w можно представить в виде w = xy, где yx принадлежит L}.
Например, если L = {01, 011}, то cycle(L) = {01, 10, 011, 110, 101}.Указание. Начните с ДКА для языка L и постройте ε-НКА для cycle(L).4.2.12. (!!) Пусть w1 = a0a0a1, а wi = wi-1wi-1ai для всех i > 0. Например, w3 =a0a0a1a0a0a1a2a0a0a1a0a0a1a2a3. Кратчайшим регулярным выражением для языкаLn = {wn}, т.е. языка, состоящего из цепочки wn, будет сама wn, причем длинаэтого выражения равна 2n+1 – 1. Однако, если применить операцию пересечения,то для языка Ln можно записать выражение длиной O(n2).
Найдите такое выражение. Указание. Найдите n языков с регулярными выражениями длины O(n),пересечение которых равно Ln.4.2.13. Свойства замкнутости можно использовать для доказательства нерегулярностинекоторых языков. Докажите, что языкL0n1n = {0n1n | n ≥ 0}нерегулярен. Докажите нерегулярность следующих языков, преобразовав их спомощью операций, сохраняющих регулярность, в язык L0n1n:а) (∗) {0i0j | i ≠ j};б) {0n1m2n-m | n ≥ m ≥ 0}.4.2.14. В теореме 4.8 представлена “конструкция произведения”, в которой по двум данным ДКА построен ДКА, допускающий пересечение языков данных автоматов:а) покажите, как построить конструкцию произведения для НКА (без ε-переходов);б) (!) продемонстрируйте, как построить конструкцию произведения для ε-НКА;в) (∗) покажите, как изменить конструкцию для произведения так, чтобы результирующий ДКА допускал разность языков двух данных ДКА;4.2.
ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂ165г) измените конструкцию для произведения так, чтобы результирующий ДКАдопускал объединение языков двух данных ДКА.4.2.15. В доказательстве теоремы 4.8 утверждалось, что с помощью индукции по длинецепочки w можно доказать следующее равенство:δˆ ((qL, qM), w) = ( δˆ L(qL, w), δˆ M(qM, w)).Приведите это доказательство.4.2.16. Завершите доказательство теоремы 4.14, рассмотрев случаи, когда выражение E является конкатенацией двух подвыражений или итерацией некоторого выражения.4.2.17. В теореме 4.16 пропущено доказательство индукцией по длине цепочки w того,)∧что γ (q0, w) = δ (q0, h(w)). Восполните этот пробел.4.3.
Ñâîéñòâà ðàçðåøèìîñòè ðåãóëÿðíûõ ÿçûêîâВ этом разделе мы сформируем важные вопросы, связанные с регулярными языками.Сначала нужно разобраться, что значит задать вопрос о некотором языке. Типичныйязык бесконечен, поэтому бессмысленно предъявлять кому-нибудь цепочки этого языкаи задавать вопрос, требующий проверки бесконечного множества цепочек.
Гораздо разумнее использовать одно из конечных представлений языка, а именно: ДКА, НКА, εНКА или регулярное выражение.Очевидно, что представленные таким образом языки будут регулярными. В действительности не существует способа представления абсолютно произвольных языков. Вследующих главах предлагаются конечные методы описания более широких классов,чем класс регулярных языков, и можно будет рассматривать вопросы о языках из них.Однако алгоритмы разрешения многих вопросов о языках существуют только для классарегулярных языков.
Эти же вопросы становятся “неразрешимыми” (не существует алгоритмов ответов на эти вопросы), если они поставлены с помощью более “выразительных” обозначений (используемых для выражения более широкого множества языков),чем представления, разработанные для регулярных языков.Начнем изучение алгоритмов для вопросов о регулярных языках, рассмотрев способы, которыми одно представление языка преобразуется в другое.
В частности, рассмотрим временную сложность алгоритмов, выполняющих преобразования. Затем рассмотрим три основных вопроса о языках.1.Является ли описываемый язык пустым множеством?2.Принадлежит ли некоторая цепочка w представленному языку?3.Действительно ли два разных описания представляют один и тот же язык? (Этот вопрос часто называют “эквивалентностью” языков.)166ÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂ4.3.1.
Ïðåîáðàçîâàíèÿ ðàçëè÷íûõ ïðåäñòàâëåíèé ÿçûêîâИз главы 3 известно, что каждое из четырех представлений регулярных языков можно преобразовать в любое из остальных трех. На рис. 3.1 представлены переходы от одного представления к другому. Хотя существуют алгоритмы для любого из этих преобразований, иногда нас интересует не только осуществимость некоторого преобразования,но и время, необходимое для его выполнения. В частности, важно отличать алгоритмы,которые занимают экспоненциальное время (время как функция от размера входныхданных) и, следовательно, могут быть выполнены только для входных данных сравнительно небольших размеров, от тех алгоритмов, время выполнения которых является линейной, квадратичной или полиномиальной с малой степенью функцией от размеравходных данных. Последние алгоритмы “реалистичны”, так как их можно выполнить длягораздо более широкого класса экземпляров задачи.
Рассмотрим временную сложностькаждого из обсуждавшихся преобразований.Преобразование НКА в ДКАВремя выполнения преобразования НКА или ε-НКА в ДКА может быть экспоненциальной функцией от количества состояний НКА. Начнем с того, что вычисление εзамыкания n состояний занимает время O(n3). Необходимо найти все дуги с меткой ε, ведущие от каждого из n состояний. Если есть n состояний, то может быть не более n2 дуг.Разумное использование системных ресурсов и хорошо спроектированные структурыданных гарантируют, что время исследования каждого состояния не превысит O(n2). Вдействительности для однократного вычисления всего ε-замыкания можно использоватьтакой алгоритм транзитивного замыкания, как алгоритм Уоршалла (Warshall)5.После вычисления ε-замыкания можно перейти к синтезу ДКА с помощью конструкции подмножеств.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
