Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 37
Текст из файла (страница 37)
Указание. Как и в упражнении 4.2.2, проще всего начать с ДКА лля Е и преобра- зовать его для получения нужного языка. (!) Если ж = а,а,...а„и х = Ь Ь,...܄— цепочки одинаковой длины, то определим ай(и, х) как цепочку, в которой символы цепочек н и х чередуются, начиная с ж, т.е.
а,Ь,азБ,...а„Ь„. Если Е и М вЂ” языки, определим ай1Е, М) как множество цепочек вида ай!ж, х), где и — произвольная цепочка из Е, а х — любая цепочка из М такой же ллины. Докажите, что из регулярности языков Е и М следует регулярность языка а!!(Е, М). 4.2.7. (!!) Упражнение 4.2.8 можно распространить на многие функции, определяющие длину части цепочки. Если ! — функция, определенная на множестве целых чисел, то обозначим через ДЕ) множество цепочек !ж ) существует цепочка х, для которой ',т( =)!!н4) и жх принадлежит Ц. Например, операция Ьа!Есоответствует тождественной функции)!и) =- л, так как для цепочек из языка Ьа!дЕ) выполняется ф = !и (. Покажите, что если язык Е регулярен, то языку!Е) также регулярен, ' гдеу' — одна из следующих функций: 4.2.9.
а) Яп) = 2л (т.е. используются первые трети цепочек); ГЛАВА 4. СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ 164 4.2.8. (ь!!) Пусть Š— язык. Определим Ьа01Е) как множество первых половин цепочек языка Е, т.е. множество !и ~ существует х, для которой вх принадлежит Е, причем ~т! = ЬгД, Например, если Е = !в, 00! О, 01 1, 0! 0! 10), то Ьа)ЯЕ) = 1в, 00. 0 10). Заметим, что цепочки с нечетной длиной не влияют на Ьа!ЯЕ). Докажите, что если язык Е регулярен, то Ьа!ДЕ) также регулярен. б) 3(л) = пп (длина выбираемой части цепочки равна квадратному корню длины оставшейся части цепочки); в) /(и) = 2" (длина выбираемой части цепочки равна логарифму длины ее остатка).
4.2,10, (1!) Пусть Š— язык, не обязательно регулярный, в алфавите (0), т.е. цепочки языка Е состоят из одних нулей. Докажите, что язык Е регулярен. Указание. На первый взгляд эта теорема кажется абсурдной. Чтобы проиллюстрировать истинность утверждения теоремы, приведем один небольшой пример. Рассмотрим язык !.
= (О' ~ ! — простое число), который, как известно, нерегулярен (см. пример 4.3). Нетрудно доказать, что если / > 2, то (У принадлежит Е . Поскольку числа 2 и 3 — простые, цепочки 00 и 000 принадлежат Е. Если / — четное число, то 0' можно получить, повторив //2 раз цепочку 00, а если/ — нечетное, можно взять одну цепочку 000 и (/' — 3)/2 цепочек 00.
Следовательно, Е = к+ 000*. 42.11. (!!) Докажите замкнутость регулярных языков относительно следующей опера- ции: сус!е(Е) = (зг ~ цепочку и можно представить в виде ж = ху, где ух принадлежит Ц. Например, если Е = (01, 011), то сус!е(Е) = (01, 10, 011, 110, 101). Указание. Начните с ДКА для языка Е и постройте к-НКА для сус/е(Е). 4,2.12.
(!!) Пусть н, = а,аеаь а и, = н,,м,.,а, для всех / > О. Например, а0аяа~а,а,а~аза,а,а,а,аяага,аь Кратчайшим регулярным выражением для языка Е„= (ж„), т.е. языка, состоящего из цепочки ж„, будет сама ж„, причем длина ы! этого выражения равна 2 — 1. Однако, если применить операцию пересечения, то для языка Е„можно записать выражение длиной 0(пз).
Найдите такое выражение. Указание. Найдите и языков с регулярными выражениями длины О/л), пересечение которых равно Е„. 42.13. Свойства замкнутости можно использовать для доказательства нерегулярности некоторых языков. Докажите, что язык Ер г = (О"1")лВО) нерегулярен. Докажите нерегулярность следующих языков, преобразовав их с помощью операций, сохраняющих регулярность, в язык Ещм. а) (я) (О'9 ! ! ~ /); б) (О"! 2" в ! и > гл > 0) . 4.2.14. В теореме 4.8 представлена "конструкция произведения", в которой по двум дан- ным ДКА построен ДКА, допускающий пересечение языков данных автоматов: а) покажите, как построить конструкцию произведения для НКА (без к-переходов); б) (!) продемонстрируйте, как построить конструкцию произведения для к-НКА; в) (1) покажите, как изменить конструкцию для произведения так, чтобы результирующий ДКА допускал разность языков двух данных ДКА; 4.2.
СВОЙСТВА ЗАМКНУТОСТИ РВТУЛЯРНЫХ ЯЗЫКОВ 165 г) измените конструкцию для произведения так, чтобы результирующий ДКА допускал объединение языков двух данных ДКА. 4.2.15. В доказательстве теоремы 4.8 утверждалось, что с помощью индукции по длине цепочки ж можно доказать следующее равенство; бИЧс,?м),ж)=(б~.(?е,и), бм(дм,ю)). Приведите это доказательство.
42.16. Завершите доказательство теоремы 4.14, рассмотрев случаи, когда выражение Е является конкатенацией двух подвыражений нли итерацией некоторого выражения. 4.2.17. В теореме 4.16 пропущено доказательство индукцией по длине цепочки и того, что у (гм, н ) — Б (су,, Ь(зг)). Восполните этот пробел.
4.3. Свойства разрешимости регулярных языков В этом разделе мы сформируем важные вопросы, связанные с регулярными языками. Сначала нужно разобраться, что значит задать вопрос о некотором языке. Типичный язык бесконечен, поэтому бессмысленно предъявлять кому-нибудь цепочки этого языка н задавать вопрос, требующий проверки бесконечного множества цепочек.
Гораздо разумнее использовать одно из конечных представлений языка, а именно; ДКА, НКА, е- НКА или регулярное выражение. Очевидно, что представленные таким образом языки будут регулярными. В действительности не существует способа представления абсолютно произвольных языков. В следующих главах предлагаются конечные методы описания более широких классов, чем класс регулярных языков, и можно будет рассматривать вопросы о языках из них. Однако алгоритмы разрешения многих вопросов о языках существуют только для класса регулярных языков.
Эти же вопросы становятся "неразрешимыми" (не существует алгоритмов ответов на эти вопросы), если они поставлены с помощью более "выразительных" обозначений (используемых для выражения более широкого множества языков), чем представления, разработанные для регулярных языков.
Начнем изучение алгоритмов для вопросов о регулярных языках, рассмотрев способы, которыми одно представление языка преобразуется в другое. В частности, рассмотрим временную сложность алгоритмов, выполняющих преобразования. Затем рассмот- рим три основных вопроса о языках.
1. Является ли описываемый язык птстым множеством? 2. Принадлежит ли некоторая цепочка эг представленному языку? 3. Действительно ли два разных описания представляют один и тот же язык? (Этот вопрос часто называют "эквивалентностью" языков.) ГЛАВА 4. СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ 4.3.!. Преобразования различных представлений языков Из главы 3 известно, что каждое из четырех представлений регулярных языков можно преобразовать в любое из остальных трех. На рис. 3.! представлены переходы от одного представления к другому. Хотя существуют алгоритмы лля любого из этих преобРаованнй, иногда нас интересует не только осуществимость некоторого преобразования, но и время, необходимое для его выполнения. В частности, важно отличать алгоритмы, которые занимают экспоненциальное время (время как функция от размера входных внвых) и, следовательно, могут быть выполнены только для входных данных сравнительно небольших размеров, от тех алгоритмов, время выполнения которых является линейной, квадратичной или полиномиальной с малой степенью функцией от размера входных данных.
Последние алгоритмы "реалистичны", так как их можно выполнить для гораздо более широкого класса экземпляров задачи. Рассмотрим временную сложность каждого из обсуждавшихся преобразований. Преобразование НКА в ДКА Время выполнения преобразования НКА или к-НКА в ДКА может быть экспоненциальиой функцией от количества состояний НКА. Начнем с того, что вычисление кммыкания и состояний занимает время 0(из).
Необходимо найти все дуги с меткой к, ведущие от каждого из и состояний. Если есть и состояний, то может быть не более ип дуг. Разумное использование системных ресурсов и хорошо спроектированные структуры 3 данных гарантируют, что время исследования каждого состояния не превысит 0(и ). В действительности для однократного вычисления всего к-замыкания можно использовать такой алгоритм транзитивного замыкания, как алгоритм Уоршалла (ЪУагьЛай) . После вычисления в-замыкания можно перейти к синтезу ДКА с помощью конструкции подмножеств. Основное влияние на расход времени оказывает количество состояний ДКА, которое может равняться 2".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
