Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 69
Текст из файла (страница 69)
Ее вторая и пятая позиции назначены 0 1, а первая, третья и четвертая — 11О. Цепочка 01110 может быть построена тремя способами: позиция 1 и одна из 2, 3, 4 назначается 01, а оставшиеся три в каждом случае — ! 10. Перемешивание языков, заир(е(Еь Ег), определяется как объединение зЬифе(и, х) по всем парам цепочек, и из Е~ их из Ей а) постройте зйиф7е(00, 111); б) (в) Укажите, что пРедставлЯет собой злиЕ)7е(Еь Ег), если Е~ = Е(0 ) и Ез = (О"!") и > 0)! в) (в!) докажите, что если Е~ и Ег — регулярные языки, то и зпиф7е(Еь Ез) регулярен. Укпзание.
Начните с конечных автоматов для Е, и Ер,' г) (!) докажите, что если Е является КС-языком, а )7 — регулярным языком, то зяифе(Е, Е) — КС-язык. Указание. Начните с МП-автомата для Е и ДКА для Е; д) (!!) приведите контрпример, показывающий, что если Ес и Ез — КС-языки, то йи)Де(Еь Е,) может не быть КС-языком.
73.5. (в!!) Цепочка у называется нересгвановкой цепочки х, если символы у можно пере- упорядочить и получить х. Например, перестановками цепочки х = 011 являются 110, 101 и 011. Если Š— язык, то регт(Е) — зто множество цепочек, являющихся перестановками цепочек из Е. Например, если Е = (О" 1" ~ н > О), то реггл(Е) представляет собой множество цепочек, в которых поровну символов 0 и 1: 7.3. СВОЙСТВА ЗАМКНУТОСТИ КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 306 а) приведите пример регулярного языка Е над алфавитом (О, 1), для которого Реги(Е) нерегулярен.
Ответ обоснуйте. Указание. Попытайтесь найти регулярный язык, перестановками цепочек которого являются все цепочки с одинаковыми количествами О и 1; б) приведите пример регулярного языка Е в алфавите (О, 1,2), для которого реги(Е) не является КС-языком; в) докажите, что для каждого регулярного языка Е в двухсимвольном алфавите Регт(Е) является КС-языком. 7.3.6. Приведите формальное доказательство теоремы 7.25 о том, что КС-языки замкнуты относительно обрашения. 7.3,7.
Дополните доказательство теоремы 727, показав, что (ч ' ° хо) 1~ (ч е у) тогда и только тогда, когла((йр, дА) и', ко) г, ((Ч Р) к у) иР= б(Рх ж). 7.4. Свойства разрешимости КС-языков Теперь рассмотрим, на какие вопросы о контекстно-свободных языках можно дать ответ. По аналогии с разделом 4.3, где речь шла о свойствах разрешимости регулярных языков, все начинается с представления КС-языка — с помошью грамматики или МП- автомата.
Поскольку из раздела 6.3 нам известно о взаимных преобразованиях грамматик и МП-автоматов, можно предполагать, что доступны оба представления, и в каждом конкретном случае будем использовать более удобное. Мы обнаружим, что разрешимых вопросов, связанных с КС-языками, совсем немного, Основное, что можно сделать, — это проверить, пуст ли язык, и принадлежит ли данная цепочка языку. Этот раздел завершается кратким обсуждением проблем, которые являются, как будет показано в главе 9, "неразрешимыми*', т.е. не имеющими алгоритма разрешения. Начнем этот раздел с некоторых замечаний о сложности преобразований между грамматиками и МП-автоматами, задающими язык. Эти расчеты важны в любом вопросе об эффективности разрешения свойств КС-языков по данному их представлению.
7,4.1. Сложность взаимных преобразований КС-грамматик и МП-автоматов Прежде чем приступать к алгоритмам разрешения вопросов о КС-языках, рассмотрим сложность преобразования одного представления в другое. Время выполнения преобразования является составной частью стоимости алгоритма разрешения в тех случаях, когда алгоритм построен для одной формы представления, а язык дан в другой. ГЛАВА 7. СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 306 В дальнейшем и будет обозначать длину представления МП-автомата или КС- грамматики. Использование этого параметра в качестве представления размера грамматики или автомата является "грубым", в том смысле, что некоторые алгоритмы имеют время выполнения, которое описывается точнее в терминах других параметров, напри- иер, число переменных в грамматике или сумма длин магазинных цепочек, встречающнхся в функции переходов МП-автомата.
Однако мера обшей длины достаточна для решения наиболее важных вопросов: является лн алгоритм линейным относительно длины входа (т.е. требует ли он времени, чуть большего, чем нужно для чтения входа), экспоненциальным (т.е, преобразование выполнимо только для примеров малого размера) или нелинейным полиномнальным (т.е, алгоритм можно выполнить даже для больших примеров, но время будет значительным). Следующие преобразования линейны, как мы увидим далее, относительно размера входных данных. 1. Преобразование КС-грамматики в МП-автомат по алгоритму из теоремы 6.13. 2. Преобразование МП-автомата, допускающего по заключительному состоянию, в МП-автомат, допускающий по пустому магазину, с помощью конструкции из теоремы 6.11.
3, Преобразование МП-автомата, допускающего по пустому магазину, в МП-автомат, допускающий по заключительному состоянию, с использованием конструкции из теоремы 6.9. С другой стороны, время преобразования МП-автомата в грамматику (теорема 6.14) существенно больше. Заметим, что и, общая длина входа, гарантированно является верхней границей числа состояний или магазинных символов, поэтому переменных вида ~Хд], построенных для грамматики, может быть не более и . Однако время выполнения н преобразования может быть экспоненциальным, если у МП-автомата есть переход, поиещаюший большое число символов в магазин.
Отметим, что одно правило может по- честить в магазин почти и символов. Если мы вспомним построение продукций грамматики по правилу вида 'огд, а, Х) содержит (гп, У~У,... Уз)", то заметим, что оно порождает набор продукций вида [9ХгД вЂ” э а[туг][г, У г]... [г~ ~ У гь] для всех последовательностей состояний гь г,, ..., гь Поскольку 1 может быть близко к и, общее число продукций возрастает как и". Такое построение невозможно довести до конца для МП-автомата разумного размера, даже если он имеет всего одну цепочку, записываемую в магазин. К счастью, этого наихудшего случая всегда можно избежать.
Как предлагалось в упражнении 6.2.8, йомешение длинной цепочки в магазин можно разбить на последовательность нз не более, чем и шагов, на каждом из которых в магазин помещается всего один символ. Таким образом, если б[д, а, Х) содержит (г,, У У,... Уз), можно ввести новые 7.4. СВОЙСТВА РАЗРКШИМОСТИ КС-ЯЗЫКОВ 307 состояния р:, рь ..., Рг ь Затем изменим (гв, У~У, ., Уг) в Щ а, л) на (р„н 3'г, Уэ) и введем новые переходы фр„ь к у~,) = ((рг л «ь уь )), Хрг ь в, )г,) = ((рг л )г ~уг )) и так далее до4р~ а уэ) = ((г,, у,Ъ'~)). Теперь в любом переходе не более двух магазинных символов. При этом добавлено не более и новых состояний, и общая длина всех правил перехода б выросла не более, чем в константу раз, т.е. осталась О(л).
Существует О(л) правил перехода, и каждое поз рождает О(л ) продукций, поскольку в продукциях, порожденных каждым правилом, должны быть выбраны всего два состояния. Таким образом, грамматика имеет длину О(л') и может быгь построена за кубическое время. Проведенный неформальный анализ резюмируется в следующей теореме. Теорема 7.31. Существует алгоритм сложности О(л ), который по МП-автомату Р строит КС-грамматику длиной не более 0(лп). Эта грамматика порождает язык, допускаел1ый Р по пустому магазину.
В дополнение, можно построить грамматику, которая порождает язык, допускаемый Р по заключительному состоянию. П 7.4.2. Временная сложность преобразования к нормальной форме Хомского Алгоритмы могут зависеть от первичного преобразования в нормальную форму Хом- ского, поэтому посмотрим на время выполнения различных алгоритмов, использованных для приведения произвольной грамматики к НФХ. Большинство шагов сохраняют, с точностью до константного сомножителя, длину описания грамматики, т.е. по грамматике длиной л они строят другую длиной О(п).
"Хорошие" (с точки зрения затрат времени) преобразования перечислены в следующем списке. 1. С использованием подходящего алгоритма (см. раздел 7.4.3) определение достижимых и порождающих символов грамматики может быть выполнено за линейное время, О(л). Удаление получившихся бесполезных символов требует О(и) времени и не увеличивает размер грамматики.
2. Построение цепных пар и удаление цепных продукций, как в разделе 7.1.4, требует времени 0(л ), и получаемая грамматика имеет размер 0(и ), 3. Замена терминалов переменными в телах продукций, как в разделе 7.1.5 (нормальная форма Хомского), требует времени 0(п) и приводит к грамматике длиной 0(л). 4. Разделение тел продукций длины 3 и более на тела длины 2 (раздел 7.1.5) также требует времени 0(л) и приводит к грамматике длиной О(л). "Плохой" является конструкция из раздела 7.1.3, где удаляются в-продукции. По телу продукции длиной х можно построить 2 — 1 продукций новой грамматики. Поскольку )г ГЛАВА 7.
СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 808 может быль пропорционально и, эта часть построения может занимать 0(2") времени и приводить к грамматике длиной О(2"). Во избежание этого экспоненциального взрыва достаточно ограничить длины тел продукций. К каждому телу продукции можно применить прием из раздела 7.1,5, но телько если в теле нет терминалов. Таким образом, в качестве предварительного шага перед удалением и-продукций рекомендуется разделить все продукции с длинными тедами на последовательность продукций с телами длины 2. Этот шаг требует времени 0(п) и увеличивает грамматику только линейно. Конструкция из раздела 7.1.3 для удачення е-продукций будет работать с телами длиной не более 2 так, что время выполнения будет 0(и) и полученная грамматика будет длиной О(и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
