Гладкий - Формальные грамматики и языки - 1973, страница 11

)' имеет место )(х) мат '(('(т(х))) (знак ~ означает совпадение областей определения и совпадение значений в каждой точке общей области определения). ОСНОВНЫЕ ПОНЯТИЯ )гл. ! Показать, что: а) понятия н. . п. м. и н. ) .р.п.м. и н.ч.р.ф. не зависят от выбора стандартной нумерапии; б) понятие н.р.п.и.

не изменяется прн расшиоенпн алфавита (точнее: если Е ': — У" и Уе†з У', то свойство языка Е быть н. р, п.м. не зависит от того, относительно которого из алфав У У' (н. ч.. ф,, в) язык (фуикиия) тогда и только тогда яв яется н. л .р.п.м. шиной. ( . . р. ф,), когда ои(а) допускается (вычисляется) некотор й Э- екоторо -маН22. Показать, что: а) для всякой ДЭ-машины, распознающей язык Е, можно построить ДЭ-машину, допускающую язык СЕ; б) если имеются ДЭ-машины, допускающие языки Е и СЕ, то по иим можно построить ДЭ-машину, распознающую Е. Заме к, ка чан не. Отсюда и из теоремы Поста след т,— у, к уже было отмечено, ДЭ-машины допускают в точности рекурсивно перечислимыс множества,— что существов ии щей язык ДЭ-машины равносильно рекурсивнасти этого языка.

ГЛАВА 2 СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ Э 2.1. Сигнализирующие функции грамматик Одним из наиболее существенных вопросов, возникающих при изучении порождающих грамматик (как в теоретическом, так и в прикладном аспекте), является вопрос об оценке сложности их работы, т. е. сложности выводов. Для оценки сложности выводов в грамматиках используются так называемые сигнализирующие функции, введением которых мы сейчас и займемся.

Пусть )(Г, Р, 1) — вычислимая функция, принимающая в качестве значений натуральные числа и определенная на всевозможных тройках (Г, Р, 1), где Г = = (У, %', 1, )т) — грамматика (причем мы считаем, что основные и вспомогательные словари всех рассматриваемых грамматик содержатся в некоторых счетных множествах Е и Ес соответственно), Р = (шз, шь ..., шв)— вывод в Г и 1= О, 1, ..., н.

Для произвольной цепочки х еи Ь(Г) и произвольного вывода Р = (шз, шь ..., шв) цепочки х из! в Г положим 1(Г, Р, х)= гпах )(Г, Р, 1). о<с<в Далее, для любой цепочки х еи Ь(Г) положим Р(Г,х) = пнп)(Г, Р,х), где минимум берется по всем выводам цепочки х из 1 в Г. Наконец, положим Р(1', а) = щах Р(Г, х); вы ь(ГЬ )л)~в для тех и, для которых ие существует таких хе= Е(Г), что )х) ( а, полагаем Р(Гг и) = О, СИГНАЛИЗИРУЮШИВ ФУНКЦИИ [ГЛ сиГнАливирующив Функции ГРАммдтик 1 к1! Так определенную функцию Р(Г,а) мы будем па,' зывать квазисигнализирующим операторо д л я г р а м м а т и к, а функцию Рг(а), получаемую н ' Р(Г, а) фиксированием переменной Г, — к в а з н с и г н а лизирую щей функцией (или просто квази сигнализирующей) типа Р грамматики Г Таким образом, квазисигнализирующий оператор Р(Г, а) сопоставляет каждой грамматике Г числовую функцию Рг (а).

Если участвующая в определении оператора функция 1(Г, Р, 1) выбрана так, чтобы она в ка-: ком-то смысле характеризовала «сложность» цепочки езг по отношению к ее «месту» в выводе Р, то функцию у(Г, Р, х) — наибольшую «1-сложность» входящей в вы-,, вод цепочки — естественно считать мерой 1'-сложности' вывода; тогда Р(Г, х) есть )-сложность самого простого' вывода цепочки х, а Р(Г, а) — наименьшее число Аг такое, что все принадлежащие й(Г) цепочки длины, непре-' восходящей а, можно вывести с )-сложностью, не пре- ' восходящей й1. Таким образом, значение оператора Р для конкретной грамматики, т.

е. ее квазисигнализирующую типа Р, можно считать определенной характеристикой сложности выводов в данной грамматике. Однако действительно пригодные для произвольных грамматик характеристики сложности выводов достав- . ляются лишь теми квазисигнализирующими операторами, которые удовлетворяют некоторому специальному условию (его значение станет нам ясно из дальнейше-; го). Это условие — рекурсивность графика соответ- ' ствующей функции Р(Г, х), т. е. существование алгоритма, позволяющего по любой тройке (Г, х, р), где Г— грамматика, х — цепочка в ее основном словаре и р— натуральное число, узнать, выполняется ли равенство Р(Г, х) = Р.

Квазисигнализирующий оператор Р(Г, а), . удовлетворяющий этому условию, мы будем называть сигнализирующим оператором для грамматик, а соответствующие квазисигналнзирующие — сигнализирующ имм и (функция м н) типа Р. Может оказаться, что некоторый квазисигнализирующий оператор, не являющийся сигнализирующим в клас- . се всех грамматик, становится таковым в некотором более частном классе. Точнее: пусть Р(Г, а) — квазисигиалпзирующий оператор, à — некоторый класс грамма. ом Р и РУ(Г а) ф кциЯ, индУциРУемаЯ опеРатоРом у- Е оответствующая функция Р~ имеет рекур- тно- снвный график, то мы будем называть Р (Г, а) о сительным сигнализирующим оператором РГ(Г, а) фиксированием переменной Г, — с и г н а л и з и- рующей (функцией) типа Р грамматики Г от- носительно У.

Мы будем рассматривать следующие основные типы квазисигнализирующих. 1. Временная сложность (обозначение Тг (а)): соответствует случаю )( Г, Р, 1) = 1. 2. Ем кость Яг (а): получается при 1(Г, Р, () = 3. Лева я глуби на Я(а): 1(1', Р, () — увеличен- ное на единицу расстояние от самого левого вхождения вспомогательного символа до правого конца гог', точнее, если езз — — х,Агт1И гДе х, ~ 1г' 1'(Г, Р, () =1гн1+ 1; если пзг ~)Г', то 1(Г, Р, 1) =О.

4. Правая глубина 9" (а): определяется сим- метрично Пгг(1 (а). 5. Р а з б р о с Рг (а): 1(Г, Р, 1) есть длина наимень- шей подцепочки ез„содержащей все вхождения вспо- могательных символов, если таковые имеются; в про- тивном случае 1 (Г, Р, 1) = О. 6. Активная ем кость 1Г (а): 1(Г, Р, 1) есть число вхо д вхождений вспомогательных символов в ыь Соответствующие квазисигнализирующие операторы будут обозначаться Т, 5, Щл, .Угп, Р, 1*), С ержательный смысл функций Тг н Зг ясен: пероде в вая характери у еризует сложность вывода числом его шаго, я — объемом затрачиваемой «памяти» (носителя- вторая — о ъ омежпамяти» в выводе естественно считать его пр . у- 5 точные цепочки).

Легко видеть, что операторы Т и сигнализирующие. Действительно, пусть заданы грамма- тика Г, цепочка х и натуральное число р. Чтобы узнать, имеет ли место равенство Т(Г, х) = р, можно поступить следующим образом. Выпишем все полные выводы в Г, ') Т, 8, Р, 1 — от 1ппе, ирисе, Шзрегцоп, 1пг1ез (пи де к с — дру. гое название активной емкости, см., например, 1С нк Сто ий 19691). СИГНЯЛИЗИРУЮШИВ ФУНКЦИИ имеющие длину р.

Если ни один из них не оканчивается цепочкой х, то заведомо Т(Г, х) Ф р. В противном случае выпишем все полные выводы в Г, длины которых меньше р. Если среди этих выводов найдется хотя бы один, оканчивающийся цепочкой х, то Т(Г, х) ~ р, а если таких выводов нет, то Т(Г, х) = р. Совершенно . аналогично проверяется выполнение равенства Я(Г,х) = = р; при этом вместо длины вывода (юа..... юя) рассматривается число шах ) юг) и берутся не произвольа<г<я ные выводы, а только бесповторные (иначе выводов с данным значением шах (со,) могло бы оказаться бесОкш <я конечно много). Ограничиться бесповторными выводами можно в силу леммы 1.3 и того, что при выбрасывании из вывода каких-либо цепочек число шах (ю;~ не 0<с<я увеличивается.

Что касается операторов фл, .',)(и, Р, ?, то ни один из ннх сигнализирующим не является. Чтобы показать это, рассмотрим произвольно грамматику Гз = = (У, ((У, ?о, )со) такую, что У = ()) и ?.(Го) = Мз— нерекурсивное множество целых положительных чисел. Положим Г1 = ((а) () У () ))У (?, Ь), ! )7с ()(! -+ ?с ) — Ь, Ь - аа)) где ?, а, Ь ф У () )у'. Добавим теперь к схеме грамматики Г~ правила ! — !', !'- ВАА, !' — ВВ, ВВ- аа, аА- аа, где !', А,  — новые символы, которые будут считаться вспомогательными. Полученная грамматика Гз порождает Язык ?.(Гз) 0 (азп)а 1, 2, ...), но пРи п ен СМа меем г(ул (1' из~) — у'и (1" изя) — Р(1 изя) ! (1' ияп)— = 2п, а при а ен Мз нн одна из этих величин не превосходит и.