Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
*) Скобки, поставленные при допускании цепочки w на ее правом конце, могут при допускании wu оказаться внутри и.
**) Ознакомившись с доказательством этой теоремы, читатель убедится, что от настоящей леммы оно не зависит.
152 Б-ГРАММАТИКИ И МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ [ГЛ. 4
г, tirtz, SiUrhsz принадлежат Cw и «происходят» от узлов с одинаковыми метками. По предыдущему отрезки г и Шг должны принадлежать и Cwu и происходить в дереве вывода цепочки wu от узлов с одинаковыми метками, какова бы ни была цепочка и такая, что wu е ^L(M). Поэтому (ср. доказательство теоремы 4.5) для любого п имеем zxsxt*rt%s2z2u е L (М).
С помощью леммы 4.15 легко доказать, что язык примера 2 на стр. 137—138 при п > 1 не допускается никакой детерминированной МП-машиной. Действительно, в противном случае для некоторой w е {аь ..., ап}* можно было бы цепочку wtib представить в виде wvb =ziylxy2z2 так, чтобы было ух ф А, у2 Ф Л и для любой цепочки
ые{а,.......ап}' имело бы место zxy"xy%z2uiiwt& е L.
Но если положить и=а[у' 1+1 »»1, где at отличен от последнего символа цепочки w, то в цепочке zxy2xxylz2udww на расстоянии 2 | w | 1 ух | +| у2 | от левого и правого
концов будут стоять разные символы.
[Стоит заметить, что «очень похожий» язык {xb?\x е {fli, ..., ап}*} допускается детерминированной МП-машиной, — например, с программой {^1 # —? q2; cj2ai-*cji+s\ fob —*? q3; qi+3 —* Aiq2\ q3cti —» ql+n+3\ q3^r -*? Qo\ Aiqi+n+з —*• 9з) (qo — единственное заключительное состояние). Символ b служит здесь сигналом к изменению направления движения рабочей головки, тогда как в предыдущем примере менять направление приходилось наугад, и поэтсШу в любой момент нужно было иметь возможность это сделать.]
Дальнейшие примеры см. в упражнении 4.34.
\
Упражнения
4.1. а) Показать, что для всякой Б-грамматики Г можно построить эквивалентную ей Б-грамматику Г', каждое правило которой либо имеет вид /->о, где I — начальный символ и а — основной символ, либо длина его правой части больше единицы.
Замечание. Очевидно, Т г, (п) < п. Поэтому 2тп (Б) = 2 (Б). Тем более 2 (Б) = 2тп (НС).
б) Показать, что для произвольной Б-грамматикн Г функция Тг(п) мажорируется линейной функцией.
4.2. Показать, что если в теореме 2.2 Г есть Б-грамматика, то и Г' можно сделать Б-гра«мати*шй.
УПРАЖНЕНИЯ
153
4.3. Оценить изменение временной сложности в конструкции леммы 4.3.
4.4. Показать, что:
а) если два вывода в Б-грамматике имеют одно н то же дерево, то они получаются друг из друга перестройкой;
б) обратное неверно (указать пример).
4.5. Указать пример НС-грамматики, в которой вывод может иметь несколько разных деревьев.
4.6. Показать, что для любой Б-грамматики можно построить эквивалентную ей Б-грамматику без правил вида А-*-В (А, В — вспомогательные символы), в которой каждый вспомогательный символ, кроме, быть может, начального, циклический.
4.7. Указать алгоритмы, позволяющие по любой Б-грамматике Г с данным основным словарем V и любой цепочке х е V* распознать, выводима ли в Г цепочка:
а) содержащая вхождение х;
б) начинающаяся с х;
в) оканчивающаяся х.
[Bar-Hillel — Perles — Shamir 1961.]
4.8. Распространить на ОБ-грамматики леммы 4.1—4.10 и теоремы 4.1, 4.2.
4.9. Показать, что языки из упражнений 3.6, 3.13, 3.20, а) не являются бесконтекстными (язык из упражнения 3.6,6)—только при k > 2, язык из упражнения 3.6, г) —только при k > 1).
4.10. Показать, что коммутативное замыкание (см. упражнение 3.7) Б-языка может не быть Б-языком.
4.11. Пользуясь теоремой 4.7, показать, что языки
[апЬпат | т, «==1,2, ...; т>п}
и
{апЬпат | т, га = 1,2, ...; тфп)
не являются бесконтекстными.
4.12. Показать, что класс ОБ-языков эффективно замкнут относительно операций левого и правого деления на цепочку.
4.13. Доказать незамкнутость класса Б-языков относительно вычитания и взятия дополнения непосредственно (построив соответствующий пример).
4.14. Проанализировав доказательство леммы 4.3, убедиться, что Б-язык тогда и только тогда является однозначным, когда он может быть порожден однозначной стандартной бинарной Б-грамматикой.
4.15. Замкнут ли класс однозначных Б-языков относительно объединения, пересечения, усеченной итерации?
4.16. Доказать неоднозначность следующих Б-языков:
а) {ambmcndn\m, га = 1, 2, .. .}[}{ambncndm | т, и = 1,2, ...};
б) {акЬтсп | k, т, п = 1, 2, ...; /г ^ fe V п^.т);
в) {akbkcmdmen \ к, т, п= 1,2,.. .}[){akbmcmdnen \ k, m, ti = 1, 2, ...}.
4.17. Замкнут ли класс неоднозначных Б-языков относительно объединения, умножения, усеченной итерации?
154 Ъ-ГРАММАТИКИ Й МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ [ГЛ. 4
4.18. а) Показать, что произведение неоднозначного Б-языка и двухэлементного языка может быть однозначным Б-языком.
б) Верен ли аналогичный факт для одноэлементного языка?
4.19. Построить Б-грамматику, порождающую язык L = =a*b,c*d*e* — L', где L' — язык из упражнения 4.16, в) [Ullian 1966]. [Указание. Представить L в виде L, U ^>2 U ?з> где L/ — = {asbhcldhl | Щ(}, причем означает ЬФ1 & g + 1фИ + /, Щ2 означает / ф / & к + j ф i + I, З13 означает g Ф h & j Ф I.]
